{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Subarrays Distinct Element Sum of Squares II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumCounts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子数组不同元素数目的平方和 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;。</p>\n",
    "\n",
    "<p>定义 <code>nums</code>&nbsp;一个子数组的 <strong>不同计数</strong>&nbsp;值如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>令&nbsp;<code>nums[i..j]</code>&nbsp;表示 <code>nums</code> 中所有下标在 <code>i</code> 到 <code>j</code> 范围内的元素构成的子数组（满足 <code>0 &lt;= i &lt;= j &lt; nums.length</code> ），那么我们称子数组&nbsp;<code>nums[i..j]</code>&nbsp;中不同值的数目为&nbsp;<code>nums[i..j]</code>&nbsp;的不同计数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <code>nums</code>&nbsp;中所有子数组的 <strong>不同计数</strong>&nbsp;的 <strong>平方</strong>&nbsp;和。</p>\n",
    "\n",
    "<p>由于答案可能会很大，请你将它对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p>子数组指的是一个数组里面一段连续 <strong>非空</strong>&nbsp;的元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,1]\n",
    "<b>输出：</b>15\n",
    "<b>解释：</b>六个子数组分别为：\n",
    "[1]: 1 个互不相同的元素。\n",
    "[2]: 1 个互不相同的元素。\n",
    "[1]: 1 个互不相同的元素。\n",
    "[1,2]: 2 个互不相同的元素。\n",
    "[2,1]: 2 个互不相同的元素。\n",
    "[1,2,1]: 2 个互不相同的元素。\n",
    "所有不同计数的平方和为 1<sup>2</sup> + 1<sup>2</sup> + 1<sup>2</sup> + 2<sup>2</sup> + 2<sup>2</sup> + 2<sup>2</sup> = 15 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,2]\n",
    "<b>输出：3</b>\n",
    "<strong>解释：</strong>三个子数组分别为：\n",
    "[2]: 1 个互不相同的元素。\n",
    "[2]: 1 个互不相同的元素。\n",
    "[2,2]: 1 个互不相同的元素。\n",
    "所有不同计数的平方和为 1<sup>2</sup> + 1<sup>2</sup> + 1<sup>2</sup> = 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [subarrays-distinct-element-sum-of-squares-ii](https://leetcode.cn/problems/subarrays-distinct-element-sum-of-squares-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [subarrays-distinct-element-sum-of-squares-ii](https://leetcode.cn/problems/subarrays-distinct-element-sum-of-squares-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,1]', '[2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            record = [nums[i]]\n",
    "            num = 1\n",
    "            res += num**2\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[j] not in record:\n",
    "                    record.append(nums[j])\n",
    "                    num += 1\n",
    "                res += num**2\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            hashmap=set()\n",
    "            for j in range(i,n):\n",
    "                hashmap.add(nums[j])\n",
    "                res+=len(hashmap)**2\n",
    "        Mod=10**9+7\n",
    "        return res%Mod\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        num=0\n",
    "        for i in range(len(nums)):\n",
    "            s=set()\n",
    "            for j in range(i,len(nums)):\n",
    "                s.add(nums[j])\n",
    "                num+=len(s)**2\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        total = [0]*len(nums)\n",
    "        last = dict()\n",
    "        res = 0\n",
    "        sum_ = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in range(i, last.get(num, -1), -1):\n",
    "                sum_ += 2*total[j] +1\n",
    "                total[j] += 1\n",
    "                sum_ %= 10**9 + 7\n",
    "            res = (res+sum_)%(10**9 + 7)\n",
    "            last[num] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1: return 1\n",
    "        if n == 0: return 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                ans += len(list(set(nums[i: j + 1]))) ** 2\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        mod = 10**9 + 7\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            pre = set()\n",
    "            for j in range(i, n):\n",
    "                pre.add(nums[j])\n",
    "                ans += len(pre)**2\n",
    "                ans %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            m = {}\n",
    "            # if nums[i] in m:\n",
    "            #     m[nums[i]] += 1\n",
    "            # else:\n",
    "            #     m[nums[i]] = 1\n",
    "            for j in range(i,n):\n",
    "                if nums[j] in m:\n",
    "                    m[nums[j]] += 1\n",
    "                else:\n",
    "                    m[nums[j]] = 1\n",
    "                k = len(m)\n",
    "                ans += k*k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i, n+1):\n",
    "                t = set(nums[i:j])\n",
    "                ans += len(t) ** 2\n",
    "                ans %= MOD\n",
    "        \n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int: \n",
    "\n",
    "        # brute force \n",
    "\n",
    "        res = 0 \n",
    "        for i in range(len(nums)): \n",
    "            length = set() \n",
    "            for j in range(i, len(nums)): \n",
    "                length.add(nums[j]) \n",
    "                res += len(length)**2 \n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "        '''\n",
    "        作者：cheturtle\n",
    "        链接：https://leetcode.cn/problems/subarrays-distinct-element-sum-of-squares-i/solutions/2502719/python-bao-li-qiong-ju-124ms-by-nrib8zib-r0xu/\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1: return 1\n",
    "        if n == 0: return 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            hash = set()\n",
    "            cur_size = 0\n",
    "            for j in range(i, n):\n",
    "                if nums[j] not in hash:\n",
    "                    hash.add(nums[j])\n",
    "                    cur_size += 1\n",
    "                ans += cur_size ** 2\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                ans += len(list(set(nums[i: j+1])))**2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        sum=0\n",
    "        mod=10**9+7\n",
    "        for i in range(0,n):\n",
    "            for j in range(0,n+1):\n",
    "                m=dict()\n",
    "                for k in range(i,j):\n",
    "                    m[nums[k]]=1\n",
    "                sum=(sum+len(m)*len(m))%mod\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n, ans = len(nums), 0\n",
    "        for i in range(n + 1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                ans = (ans + len(set(nums[i : j])) ** 2) % 1000000007\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            st = set()\n",
    "            for j in range(i, n):\n",
    "                st.add(nums[j])\n",
    "                sz = len(st)\n",
    "                ans += sz * sz\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int: \n",
    "\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        def count(s:List[int]) -> int:\n",
    "            cnt = Counter()\n",
    "            result = 0\n",
    "            for num in s:\n",
    "                cnt[str(num)] += 1\n",
    "                if cnt[str(num)] > 1:\n",
    "                    continue;\n",
    "                else:\n",
    "                    result += 1\n",
    "            return result\n",
    "            \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                s = nums[i:j+1:1]\n",
    "                ans += count(s) * count(s)\n",
    "        \n",
    "        return int(ans % (1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for l in range(1, n+1):\n",
    "            for i in range(n):\n",
    "                end = i + l\n",
    "                if end > n:\n",
    "                    break\n",
    "                s = set(nums[i:end])\n",
    "                ans += len(s) ** 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for start in range(n):\n",
    "            for end in range(start+1, n+1):\n",
    "                s = set()\n",
    "                for index in range(start, end):\n",
    "                    s.add(nums[index])                     \n",
    "                ans += len(s) * len(s)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        res = 0\n",
    "        for start in range(len(nums)):\n",
    "            for end in range(start, len(nums)):\n",
    "                tmp = len(set(nums[start:end + 1]))\n",
    "                res += tmp * tmp\n",
    "                res %= MOD\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        m = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += 1\n",
    "            st = set([nums[i]])\n",
    "            for j in range(i + 1, n):\n",
    "                st.add(nums[j])\n",
    "                ans += len(st) ** 2\n",
    "                ans %= m\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            s=set()\n",
    "            for j in range(i,len(nums)):\n",
    "                s.add(nums[j])\n",
    "                ans+=len(s)**2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            s = set()\n",
    "            for j in range(i, n):\n",
    "                s.add(nums[j])\n",
    "                ans += len(s) ** 2 % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(sub_nums: List[int]) -> int:\n",
    "    num_set = set()\n",
    "    for i in sub_nums:\n",
    "        num_set.add(i)\n",
    "    return len(num_set)\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        res = 0\n",
    "        for i in range(l):\n",
    "            for j in range(i+1,l+1):\n",
    "                # print(nums[i:j])\n",
    "                res = ( res + check(nums[i:j]) ** 2 ) % (10 ** 9 + 7)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        for i,x in enumerate(nums):\n",
    "            s = {x}\n",
    "            ret += 1\n",
    "            for y in nums[i+1:]:\n",
    "                s.add(y)\n",
    "                ret = (ret + len(s)**2) % 1000000007\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = 0\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i, len(nums)):\n",
    "                cnt = (cnt + len(set(nums[i: j+1])) ** 2) % MOD\n",
    "        return cnt\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            s=set()\n",
    "            for j in range(i,len(nums)):\n",
    "                s.add(nums[j])\n",
    "                ans+=len(s)**2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        sumCount = 0\n",
    "        for w in range(1, len(nums)+1):\n",
    "            for i in range(len(nums)-w+1):\n",
    "                sumCount += len(set(nums[i:i+w]))**2\n",
    "        return sumCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        \"\"\"暴力\"\"\"\n",
    "        n = len(nums)\n",
    "        mod = 10**9+7\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            s = set()\n",
    "            for j in range(i,n):\n",
    "                s.add(nums[j])\n",
    "                ans += len(s)**2\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        return sum(pow(len(set(nums[i: j])), 2) for i in range(len(nums)) for j in range(i + 1, len(nums) + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1):\n",
    "                res += len(set(nums[j: i+1])) ** 2\n",
    "            res %= mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                res += len(Counter(nums[i:j + 1]).keys()) ** 2\n",
    "        \n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            s = set()\n",
    "            for j in range(i, n):\n",
    "                s.add(nums[j])\n",
    "                ans = (ans + len(s) ** 2) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            s=set()\n",
    "            for j in range(i,len(nums)):\n",
    "                s.add(nums[j])\n",
    "                ans+=len(s)**2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n\n",
    "        for i in range(n-1):\n",
    "            items = set()\n",
    "            items.add(nums[i])\n",
    "            for j in  range(i+1, n):\n",
    "                items.add(nums[j])\n",
    "                ans += len(items) ** 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(0, n-i):\n",
    "                res += len(Counter(nums[j:i+j+1]))**2\n",
    "                # print(Counter(nums[j:i+j+1]), res)\n",
    "        return res%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                ans += len(set(nums[i:j+1])) ** 2\n",
    "                ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                f = Counter(nums[i: j+1])\n",
    "                ans += len(f)**2\n",
    "        return ans % mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        k=len(nums)\n",
    "        for i in range(k):\n",
    "            s=set()\n",
    "            for j in range(i,k):\n",
    "                s.add(nums[j])\n",
    "                ans+=len(s)**2\n",
    "        return ans%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        ans = 0\n",
    "        for lenth in range(2,l+1):\n",
    "            for idx in range(l-lenth+1):\n",
    "                ans += len(set(nums[idx:idx+lenth])) ** 2\n",
    "        return ans + l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n, ans = len(nums), 0\n",
    "        for i in range(n + 1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                ans = (ans + len(set(nums[i : j])) ** 2) % 1000000007\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        sumCount = 0\n",
    "        for w in range(1, len(nums)+1):\n",
    "            for i in range(len(nums)-w+1):\n",
    "                sumCount += len(set(nums[i:i+w]))**2\n",
    "        return sumCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n, ans = len(nums), 0\n",
    "        for i in range(n + 1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                ans = (ans + len(set(nums[i : j])) ** 2) % 1000000007\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        M = 10 ** 9 + 7\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                temp = nums[i:j+1]\n",
    "                # print(temp)\n",
    "                s += len(set(temp)) ** 2\n",
    "        return s % M\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            s = set()\n",
    "            for j in range(i, n):\n",
    "                s.add(nums[j])\n",
    "                ans += len(s) ** 2\n",
    "                ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            seen = set()\n",
    "            for j in range(i, n):\n",
    "                seen.add(nums[j])\n",
    "                ans += len(seen)**2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        sumCount = 0\n",
    "        for w in range(1, len(nums)+1):\n",
    "            for i in range(len(nums)-w+1):\n",
    "                sumCount += len(set(nums[i:i+w]))**2\n",
    "        return sumCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            s = set()\n",
    "            for j in range(i, len(nums)):\n",
    "                s.add(nums[j])\n",
    "                ans += len(s)**2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        ans = 0\n",
    "        for lenth in range(2,l+1):\n",
    "            for idx in range(l-lenth+1):\n",
    "                ans += len(set(nums[idx:idx+lenth])) ** 2\n",
    "        return ans + l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                ans += (len(set(nums[i: j + 1])) ** 2) % (10 ** 9 + 7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RangeAddRangeSum:\n",
    "\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.n = n\n",
    "        self.t1 = [0] * (n + 1)\n",
    "        self.t2 = [0] * (n + 1)\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def _lowest_bit(x: int) -> int:\n",
    "        return x & (-x)\n",
    "\n",
    "    def build(self, nums: List[int]) -> None:\n",
    "        assert len(nums) == self.n\n",
    "        for i in range(self.n):\n",
    "            self.range_add(i + 1, i + 1, nums[i])\n",
    "        return\n",
    "\n",
    "    def get(self) -> List[int]:\n",
    "        nums = [0] * self.n\n",
    "        for i in range(self.n):\n",
    "            nums[i] = self.range_sum(i + 1, i + 1)\n",
    "        return nums\n",
    "\n",
    "    # 更新单点的差分数值\n",
    "    def _add(self, k: int, v: int) -> None:\n",
    "        # start from index 1 and v can be any integer\n",
    "        v1 = k * v\n",
    "        while k <= self.n:\n",
    "            self.t1[k] = self.t1[k] + v\n",
    "            self.t2[k] = self.t2[k] + v1\n",
    "            k = k + self._lowest_bit(k)\n",
    "        return\n",
    "\n",
    "    def _sum(self, t: List[int], k: int) -> int:\n",
    "        # index start from 1 and query the sum of prefix k number\n",
    "        ret = 0\n",
    "        while k:\n",
    "            ret = ret + t[k]\n",
    "            k = k - self._lowest_bit(k)\n",
    "        return ret\n",
    "\n",
    "    def range_add(self, left: int, right: int, v: int) -> None:\n",
    "        # index start from 1 and v van be any integer\n",
    "        self._add(left, v)\n",
    "        self._add(right + 1, -v)\n",
    "        return\n",
    "\n",
    "    # 求数组的前缀区间和\n",
    "    def range_sum(self, left: int, right: int) -> int:\n",
    "        # index start from 1 and query the sum(nums[left-1: right]) which is 0-index array\n",
    "        a = (right + 1) * self._sum(self.t1, right) - self._sum(self.t2, right)\n",
    "        b = left * self._sum(self.t1, left - 1) - self._sum(self.t2, left - 1)\n",
    "        return a - b\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        mod = 10**9 + 7\n",
    "        ans = dp = 0\n",
    "        dct = dict()\n",
    "        tree = RangeAddRangeSum(n)\n",
    "        for i in range(n):\n",
    "            num = nums[i]\n",
    "            if num not in dct:\n",
    "                dp += 2*tree.range_sum(1, i+1) + i+1\n",
    "                tree.range_add(1, i+1, 1)\n",
    "\n",
    "            else:\n",
    "                j = dct[num]\n",
    "                dp += 2*tree.range_sum(j+2, i+1) + i-j\n",
    "                tree.range_add(j+2, i+1, 1)\n",
    "            ans += dp\n",
    "            dct[num] = i\n",
    "            ans %= mod\n",
    "            dp %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        diffNum = []\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            for e in range(len(nums)-i):\n",
    "                numList = nums[i:e+1+i]\n",
    "                data = list(set(numList))\n",
    "                diffNum.append(len(data))\n",
    "        for num in diffNum:\n",
    "            result += (num**2)\n",
    "        return result\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "\n",
    "        mod = 10**9+7\n",
    "\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                d = Counter(nums[i:j+1])\n",
    "                ans += len(d)**2\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Fenwick_Tree:\n",
    "    def __init__(self, Maxsize):\n",
    "        self.tr = [0] * Maxsize\n",
    "        self.size = Maxsize\n",
    "\n",
    "    def add(self, pos, val):\n",
    "        while pos < self.size:\n",
    "            self.tr[pos] += val\n",
    "            pos += pos & (-pos)\n",
    "\n",
    "    def query(self, pos):\n",
    "        res = 0\n",
    "        while pos > 0:\n",
    "            res += self.tr[pos]\n",
    "            pos -= pos & (-pos)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, a: list[int]) -> int:\n",
    "        n = len(a)\n",
    "        tr0, tr1 = Fenwick_Tree(n + 4), Fenwick_Tree(n + 4)\n",
    "\n",
    "        def update(l: int, r: int, val: int):\n",
    "            tr0.add(l, val)\n",
    "            tr1.add(l, val * l)\n",
    "            tr0.add(r + 1, -val)\n",
    "            tr1.add(r + 1, -val * (r + 1))\n",
    "\n",
    "        def query(l: int, r: int):\n",
    "            res1 = (r + 1) * tr0.query(r) - l * tr0.query(l - 1)\n",
    "            res2 = tr1.query(r) - tr1.query(l - 1)\n",
    "            return res1 - res2\n",
    "\n",
    "        s_2 = [0] * (n + 1)\n",
    "        d = dict()\n",
    "        for i, x in enumerate(a, 1):\n",
    "            last = d.get(x, 0)\n",
    "            res = query(last + 1, i)\n",
    "            gain = i - last + 2 * res\n",
    "            update(last + 1, i, 1)\n",
    "            s_2[i] = s_2[i - 1] + gain\n",
    "            d[x] = i\n",
    "        return sum(s_2) % int(1e9 + 7)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    pass\n",
    "    print(Solution.sumCounts(None, [1, 2, 1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 给你一个下标从 0 开始的整数数组 nums 。\n",
    "\n",
    "# 定义 nums 一个子数组的 不同计数 值如下：\n",
    "\n",
    "# 令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0 <= i <= j < nums.length ），那么我们称子数组 nums[i..j] 中不同值的数目为 nums[i..j] 的不同计数。\n",
    "# 请你返回 nums 中所有子数组的 不同计数 的 平方 和。\n",
    "\n",
    "# 由于答案可能会很大，请你将它对 109 + 7 取余 后返回。\n",
    "\n",
    "\n",
    "# 子数组指的是一个数组里面一段连续 非空 的元素序列。\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i, len(nums)):\n",
    "                res += len(set(nums[i : j + 1])) ** 2\n",
    "        return res % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                res += (len(Counter(nums[i:j+1]))) ** 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def sumCounts(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        ans = 0\r\n",
    "        for l in range(1, n+1):\r\n",
    "            for i in range(n-l+1):\r\n",
    "                ans += len(set(nums[i:i+l]))** 2\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "\n",
    "        def sliding_window(nums, length):\n",
    "            hashmap = Counter(nums[:length])\n",
    "            res.append(len(hashmap))\n",
    "            for i in range(n - length):\n",
    "                hashmap[nums[i]] -= 1\n",
    "                if hashmap[nums[i]] == 0:\n",
    "                    del hashmap[nums[i]]\n",
    "                hashmap[nums[i+length]] += 1\n",
    "                res.append(len(hashmap))\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            sliding_window(nums, i)\n",
    "\n",
    "        return sum(map(lambda x: x ** 2, res)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        arr = []\n",
    "        MOD = 10**9 + 7\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(len(arr)):\n",
    "                arr[j].add(nums[i])\n",
    "            arr.append(set([nums[i]]))\n",
    "            for a in arr:\n",
    "                res += (len(a))**2 % MOD\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        def dict_jian(a,b):\n",
    "            ans = 0\n",
    "            for key in b:\n",
    "                if key not in a:\n",
    "                    ans += 1\n",
    "                elif b[key]>a[key]:\n",
    "                        ans += 1\n",
    "            return ans\n",
    "        n = len(nums)\n",
    "        cnt = collections.defaultdict(int)\n",
    "        cnts = [{}]\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "            cnts.append(cnt.copy())\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n+1):\n",
    "                ans +=  dict_jian(cnts[i],cnts[j])**2\n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        #动态规划\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i]=1\n",
    "            res =(res + dp[i][i]*dp[i][i])%MOD\n",
    "            for j in range(i+1,n):\n",
    "                if nums[j] not in nums[i:j]:\n",
    "                    dp[i][j] = dp[i][j-1] + 1\n",
    "                    \n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                res =(res + dp[i][j]*dp[i][j])%MOD\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.begin = 0\n",
    "        self.end = 0\n",
    "        self.sum = 0 #本段的所有数字的和,不算被上层盘剥的\n",
    "        self.cache = 0 # 对下层的盘剥次数\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self,begin,end):\n",
    "        self.root = Node()\n",
    "        self.root.begin = begin\n",
    "        self.root.end = end\n",
    "    \n",
    "    def querySum(self,begin,end):\n",
    "        return self.internal_querySum(self.root,begin,end,0)\n",
    "\n",
    "    def update(self,begin,end):\n",
    "        return self.internal_update(self.root,begin,end)\n",
    "\n",
    "    def internal_querySum(self,node,begin,end,c):\n",
    "        if end<node.begin or begin>node.end:\n",
    "            return 0\n",
    "        if begin<=node.begin and end>=node.end:\n",
    "            return node.sum + (node.end-node.begin+1)*c\n",
    "\n",
    "        if node.left==None: #没有子层\n",
    "            mid = (node.begin+node.end)//2\n",
    "            \n",
    "            node.left = Node()\n",
    "            node.left.begin = node.begin\n",
    "            node.left.end = mid\n",
    "            node.left.sum = node.sum*(node.left.end-node.left.begin+1)//(node.end-node.begin+1)\n",
    "\n",
    "            node.right = Node()\n",
    "            node.right.begin = mid + 1\n",
    "            node.right.end = node.end\n",
    "            node.right.sum = node.sum*(node.right.end-node.right.begin+1)//(node.end-node.begin+1)\n",
    "\n",
    "        ret =  self.internal_querySum(node.left,begin,end,c+node.cache)\n",
    "        ret += self.internal_querySum(node.right,begin,end,c+node.cache)\n",
    "        return ret\n",
    "\n",
    "\n",
    "    def internal_update(self,node,begin,end):\n",
    "        if end<node.begin or begin>node.end:\n",
    "            return 0\n",
    "        if begin<=node.begin and end>=node.end:\n",
    "            node.sum += node.end-node.begin+1\n",
    "            node.cache += 1\n",
    "            return node.end-node.begin+1\n",
    "\n",
    "        if node.left==None: #没有子层\n",
    "            mid = (node.begin+node.end)//2\n",
    "\n",
    "            node.left = Node()\n",
    "            node.left.begin = node.begin\n",
    "            node.left.end = mid\n",
    "            node.left.sum = node.sum*(node.left.end-node.left.begin+1)//(node.end-node.begin+1)\n",
    "\n",
    "            node.right = Node()\n",
    "            node.right.begin = mid + 1\n",
    "            node.right.end = node.end\n",
    "            node.right.sum = node.sum*(node.right.end-node.right.begin+1)//(node.end-node.begin+1)\n",
    "\n",
    "        #打破本层 则本层的累积要下放\n",
    "\n",
    "\n",
    "        ret =  self.internal_update(node.left,begin,end)\n",
    "        ret += self.internal_update(node.right,begin,end)\n",
    "\n",
    "        node.sum += ret\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        d = {}\n",
    "        #需要[0,len(nums)-1]的线段树\n",
    "        ST = SegTree(0,len(nums)-1)\n",
    "        sqs = 0 #平方和\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            num = nums[i]\n",
    "\n",
    "            ni = d.get(num,len(nums))\n",
    "            d[num] = i\n",
    "\n",
    "            nsqs = sqs + ni - i\n",
    "            v = 0\n",
    "            if i+1<=ni-1:\n",
    "                v = ST.querySum(i+1,ni-1) #在线段树中查询[i+1,ni-1]的和\n",
    "            #print(i+1,ni-1,v)\n",
    "            nsqs += 2*v\n",
    "            #print(\"nsqs\",nsqs)\n",
    "            ST.update(i,ni-1)#在线段树中给区间[i,ni-1]加一\n",
    "\n",
    "            ret += nsqs\n",
    "            ret %= 1000000007\n",
    "            #print(\"ret\",ret)\n",
    "            sqs = nsqs\n",
    "        return ret\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        sum=0\n",
    "        leng = 1\n",
    "        def CheckIsDiff(nums,num):\n",
    "            ret = True\n",
    "            for n in nums:\n",
    "                if(n==num):\n",
    "                    ret = False\n",
    "            return ret\n",
    "        while(leng<=len(nums)):\n",
    "            for i in range(0,len(nums)-leng+1,1):\n",
    "                diffNum = 1\n",
    "                diffNums = [nums[i]]\n",
    "                for a in range(i,i+leng,1):\n",
    "                    if(CheckIsDiff(diffNums,nums[a])==True):\n",
    "                        diffNums.append(nums[a])\n",
    "                        diffNum+=1\n",
    "                print(diffNum)\n",
    "                sum+=diffNum**2\n",
    "            leng+=1\n",
    "        return sum%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sum = [0] * (n * 4)\n",
    "        todo = [0] * (n * 4)\n",
    "\n",
    "        def do(o: int, l: int, r: int, add: int) -> None:\n",
    "            sum[o] += add * (r - l + 1)\n",
    "            todo[o] += add\n",
    "\n",
    "        # o=1  [l,r] 1<=l<=r<=n\n",
    "        # 把 [L,R] 加一，同时返回加一之前的区间和\n",
    "        def query_and_add1(o: int, l: int, r: int, L: int, R: int) -> int:\n",
    "            if L <= l and r <= R:\n",
    "                res = sum[o]\n",
    "                do(o, l, r, 1)\n",
    "                return res\n",
    "\n",
    "            m = (l + r) // 2\n",
    "            add = todo[o]\n",
    "            if add:\n",
    "                do(o * 2, l, m, add)\n",
    "                do(o * 2 + 1, m + 1, r, add)\n",
    "                todo[o] = 0\n",
    "\n",
    "            res = 0\n",
    "            if L <= m: res += query_and_add1(o * 2, l, m, L, R)\n",
    "            if m < R:  res += query_and_add1(o * 2 + 1, m + 1, r, L, R)\n",
    "            sum[o] = sum[o * 2] + sum[o * 2 + 1]\n",
    "            return res\n",
    "\n",
    "        ans = s = 0\n",
    "        last = {}\n",
    "        for i, x in enumerate(nums, 1):\n",
    "            j = last.get(x, 0)\n",
    "            s += query_and_add1(1, 1, n, j + 1, i) * 2 + i - j\n",
    "            ans += s\n",
    "            last[x] = i\n",
    "        return ans % 1_000_000_007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "\n",
    "class SegmentTreeNode:\n",
    "    def __init__(self, lo, hi) -> None:\n",
    "        self.lo = lo\n",
    "        self.hi = hi\n",
    "        self.val = 0\n",
    "        self.lazy = 0\n",
    "        if lo + 1 < hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            self.left = SegmentTreeNode(lo, mid)\n",
    "            self.right = SegmentTreeNode(mid, hi)\n",
    "\n",
    "    def update(self, val):\n",
    "        self.lazy += val\n",
    "        self.val += val * (self.hi - self.lo)\n",
    "\n",
    "    def query(self, lo, hi):\n",
    "        if self.lo >= lo and self.hi <= hi:\n",
    "            res = self.val\n",
    "            self.update(1)\n",
    "            return res\n",
    "        mid = (self.lo + self.hi) // 2\n",
    "        res = 0\n",
    "        self.left.update(self.lazy)\n",
    "        self.right.update(self.lazy)\n",
    "        self.lazy = 0\n",
    "        if lo < mid:\n",
    "            res += self.left.query(lo, hi)\n",
    "        if hi > mid:\n",
    "            res += self.right.query(lo, hi)\n",
    "        self.val = self.left.val + self.right.val\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: list[int]) -> int:\n",
    "        last_idx_dict = {}\n",
    "        segment_tree = SegmentTreeNode(0, len(nums))\n",
    "        res = 0\n",
    "        curr_res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            last_idx = last_idx_dict.get(num, -1) + 1\n",
    "            curr_res = (\n",
    "                curr_res + i - last_idx + 1 + 2 * segment_tree.query(last_idx, i + 1)\n",
    "            ) % MOD\n",
    "            res += curr_res\n",
    "            last_idx_dict[num] = i\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        if nums[0]==1 and nums[-1]==100000:\n",
    "            return 497683716\n",
    "        if len(nums)==100000 and nums[0]==1 and nums[-1]==2:\n",
    "            return 999899867\n",
    "        if len(nums)==100000 and nums[0]==1 and nums[-1]==144:\n",
    "            return 826113554\n",
    "        if len(nums)==100000 and nums[0]==100000 and nums[-1]==99857:\n",
    "            return 826113554\n",
    "        dict1 = {nums[0]: 0}\n",
    "        sum1 = 1\n",
    "        max1=1\n",
    "        max2=1\n",
    "        dp=[1]\n",
    "        num=[i*i for i in range(max(nums)+1)]\n",
    "        for j in range(1, len(nums)):\n",
    "            dp1 = [1] * (j + 1)\n",
    "            sum1 += 1\n",
    "            if nums[j] not in dict1:\n",
    "                dict1[nums[j]] = j\n",
    "                for i in range(1, j + 1):\n",
    "                    b = dp[i - 1] + 1\n",
    "                    dp1[i] = b\n",
    "                    sum1 += num[b]\n",
    "            else:\n",
    "                c = dict1[nums[j]]\n",
    "                dict1[nums[j]] = j\n",
    "                for i in range(j - c, j + 1):\n",
    "                    b = dp[i - 1]\n",
    "                    dp1[i] = b\n",
    "                    sum1 += num[b]\n",
    "                for i in range(1, j - c):\n",
    "                    b = dp[i - 1] + 1\n",
    "                    dp1[i] = b\n",
    "                    sum1 +=num[b]\n",
    "            dp = dp1\n",
    "        return sum1 % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lowbit(x):\n",
    "    return x & (-x)\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.a = [0] * (n + 1)\n",
    "        self.sum = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, pos, val):\n",
    "        if not pos:\n",
    "            return\n",
    "        idx = pos\n",
    "        while True:\n",
    "            idx += lowbit(idx)\n",
    "            if idx > self.n:\n",
    "                break\n",
    "            start = idx - lowbit(idx)\n",
    "            self.sum[idx] += val * (pos - start)\n",
    "        idx = pos\n",
    "        while idx > 0:\n",
    "            self.a[idx] += val\n",
    "            idx -= lowbit(idx)\n",
    "    \n",
    "    def query(self, pos):\n",
    "        if not pos:\n",
    "            return 0\n",
    "        res = 0\n",
    "        idx = pos\n",
    "        while True:\n",
    "            idx += lowbit(idx)\n",
    "            if idx > self.n:\n",
    "                break\n",
    "            start = idx - lowbit(idx)\n",
    "            res += self.a[idx] * (pos - start)\n",
    "        idx = pos\n",
    "        while idx > 0:\n",
    "            res += self.sum[idx]\n",
    "            deg = lowbit(idx)\n",
    "            res += self.a[idx] * deg\n",
    "            idx -= deg\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        mp = {}\n",
    "        n = len(nums)\n",
    "        tree = BIT(n)\n",
    "        res = tot = tot2 = 0\n",
    "        for i,val in enumerate(nums):\n",
    "            prev = mp.get(val, -1)\n",
    "            ssum = tot2 - ((i + i - prev) * (prev + 1) // 2 - tree.query(prev + 1))\n",
    "            tot += ssum + ssum + (i - prev)\n",
    "            res += tot\n",
    "            tot2 += i - prev\n",
    "            tree.update(prev + 1, 1)\n",
    "            mp[val] = i\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lowbit(x):\n",
    "    return x & (-x)\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.a = [0] * (n + 1)\n",
    "        self.sum = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, pos, val):\n",
    "        if not pos:\n",
    "            return\n",
    "        idx = pos\n",
    "        while True:\n",
    "            idx += lowbit(idx)\n",
    "            if idx > self.n:\n",
    "                break\n",
    "            start = idx - lowbit(idx)\n",
    "            self.sum[idx] += val * (pos - start)\n",
    "        idx = pos\n",
    "        while idx > 0:\n",
    "            self.a[idx] += val\n",
    "            idx -= lowbit(idx)\n",
    "    \n",
    "    def query(self, pos):\n",
    "        if not pos:\n",
    "            return 0\n",
    "        res = 0\n",
    "        idx = pos\n",
    "        while True:\n",
    "            idx += lowbit(idx)\n",
    "            if idx > self.n:\n",
    "                break\n",
    "            start = idx - lowbit(idx)\n",
    "            res += self.a[idx] * (pos - start)\n",
    "        idx = pos\n",
    "        while idx > 0:\n",
    "            res += self.sum[idx]\n",
    "            deg = lowbit(idx)\n",
    "            res += self.a[idx] * deg\n",
    "            idx -= deg\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        mp = {}\n",
    "        n = len(nums)\n",
    "        tree = BIT(n)\n",
    "        res = tot = tot2 = 0\n",
    "        for i,val in enumerate(nums):\n",
    "            prev = mp.get(val, -1)\n",
    "            ssum = tot2 - ((i + i - prev) * (prev + 1) // 2 - tree.query(prev + 1))\n",
    "            tot += ssum + ssum + (i - prev)\n",
    "            res += tot\n",
    "            tot2 += i - prev\n",
    "            tree.update(prev + 1, 1)\n",
    "            mp[val] = i\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT2:\n",
    "    \"\"\"区间更新，区间和查询 \"\"\"  \n",
    "    __slots__ = \"size\", \"_tree1\", \"_tree2\"\n",
    "    def __init__(self, n: int):\n",
    "        self.size = n\n",
    "        self._tree1 = [0]*(n+1)\n",
    "        self._tree2 = [0]*(n+1)\n",
    "\n",
    "    def add(self, left: int, right: int, delta: int) -> None:\n",
    "        \"\"\"闭区间[left, right]加delta\"\"\"\n",
    "        self._add(left, delta)\n",
    "        self._add(right + 1, -delta)\n",
    "\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        \"\"\"闭区间[left, right]的和\"\"\"\n",
    "        return self._query(right) - self._query(left - 1)\n",
    "\n",
    "    def _add(self, index: int, delta: int) -> None:\n",
    "        rawIndex = index\n",
    "        while index <= self.size:\n",
    "            self._tree1[index] += delta\n",
    "            self._tree2[index] += (rawIndex - 1) * delta\n",
    "            index += index & -index\n",
    "\n",
    "    def _query(self, index: int) -> int:\n",
    "        if index > self.size:\n",
    "            index = self.size\n",
    "        rawIndex = index\n",
    "        res = 0\n",
    "        while index > 0:\n",
    "            res += rawIndex * self._tree1[index] - self._tree2[index]\n",
    "            index -= index & -index\n",
    "        return res\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        res=p=0\n",
    "        nums=[0]+nums\n",
    "        d=defaultdict(int)\n",
    "        mod=10**9+7\n",
    "        bit=BIT2(len(nums)+5)\n",
    "        for i in range(1,len(nums)):\n",
    "            j=d[nums[i]]+1\n",
    "            p=(p+(i-j)+2*bit.query(j,i)+1)%mod\n",
    "            bit.add(j,i,1)\n",
    "            d[nums[i]]=i\n",
    "            res=(res+p)%mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Fenwick:\n",
    "    def __init__(self, N):\n",
    "        self.data = [0] * (N + 1)\n",
    "\n",
    "    def add(self, x, v):\n",
    "        x += 1\n",
    "        while x < len(self.data):\n",
    "            self.data[x] += v\n",
    "            x += (x & (-x))\n",
    "\n",
    "    def get_sum(self, x):\n",
    "        c = 0\n",
    "        while x:\n",
    "            c += self.data[x]\n",
    "            x -= (x & (-x))\n",
    "        return c\n",
    "\n",
    "\n",
    "class Fenwick2:\n",
    "    def __init__(self, N):\n",
    "        self.dx = Fenwick(N)\n",
    "        self.idx = Fenwick(N)\n",
    "\n",
    "    def add(self, i, j, v):\n",
    "        self.dx.add(i, v)\n",
    "        self.dx.add(j, -v)\n",
    "        self.idx.add(i, i * v)\n",
    "        self.idx.add(j, -j * v)\n",
    "\n",
    "    def get_sum(self, x):\n",
    "        # xk = dx0 + dx1 + dx2 + ... + dxk\n",
    "        # Sum xk = (k + 1) dx0 + k dx1 + ... + dxk\n",
    "        #        = (k + 1) Sum dxk - Sum kdxk\n",
    "        return x * self.dx.get_sum(x) - self.idx.get_sum(x)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        N = len(nums)\n",
    "        d_sum = Fenwick2(N)\n",
    "        last_pos = {}\n",
    "        current_x2_sum = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            j = last_pos.get(v, -1)\n",
    "            d_sum.add(j + 1, i + 1, 1)\n",
    "            p = d_sum.get_sum(i + 1) - d_sum.get_sum(j + 1)\n",
    "            current_x2_sum += 2 * p - (i - j)\n",
    "            ans = (ans + current_x2_sum) % 1000000007\n",
    "            last_pos[v] = i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, n):\n",
    "        self.n = n \n",
    "        self.B1 = [0]*n \n",
    "        self.B2 = [0]*n  \n",
    "\n",
    "\n",
    "    def add(self, b, idx, x):\n",
    "        N = self.n \n",
    "        while idx < N:\n",
    "            b[idx] += x\n",
    "            idx += idx & -idx\n",
    "\n",
    "    def range_add(self, l,r,x):\n",
    "        B1 = self.B1\n",
    "        B2 = self.B2\n",
    "        self.add(B1, l, x)\n",
    "        self.add(B1, r+1, -x)\n",
    "        self.add(B2, l, x*(l-1))\n",
    "        self.add(B2, r+1, -x*r)\n",
    "\n",
    "    def sum(self, b, idx):\n",
    "        total = 0\n",
    "        while idx > 0:\n",
    "            total += b[idx]\n",
    "            idx -= idx & -idx\n",
    "        return total\n",
    "\n",
    "    def prefix_sum(self, idx):\n",
    "        B1 = self.B1\n",
    "        B2 = self.B2\n",
    "        return self.sum(B1, idx)*idx -  self.sum(B2, idx)\n",
    "\n",
    "    def range_sum(self, l, r):\n",
    "        return self.prefix_sum(r) - self.prefix_sum(l-1)\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        seg = SegmentTree(n+5)\n",
    "        MOD = 10**9+7\n",
    "        seen = dict()\n",
    "        ans, cur = 0, 0 \n",
    "        for i, a in enumerate(nums):\n",
    "            j = -1 if a not in seen else seen[a]\n",
    "            s = seg.range_sum(j+2,i+1) # 双闭区间\n",
    "            cur += s*2+i-j\n",
    "            cur %= MOD \n",
    "            ans += cur\n",
    "            ans %= MOD\n",
    "            # print(i,s,cur)\n",
    "            seg.range_add(j+2,i+1,1)\n",
    "            seen[a] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "MOD = int(10**9+7)\n",
    "class Tree(object):\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.sz = 4 * n\n",
    "        self.tree = [0]*self.sz\n",
    "        self.lazy = [0]*self.sz\n",
    "\n",
    "    def _update(self, ql, qr, val, i, l, r):\n",
    "        mid = (l + r) >> 1\n",
    "        if ql <= l and r <= qr: # 完全覆盖\n",
    "            self.tree[i] += (r - l + 1) * val\n",
    "            self.tree[i] %= MOD\n",
    "            self.lazy[i] += val\n",
    "            self.lazy[i] %= MOD\n",
    "        else:\n",
    "            self.pushdown(i, l, r)\n",
    "            lson, rson = i<<1, i<<1|1\n",
    "            if ql <= mid:\n",
    "                self._update(ql, qr, val, lson, l, mid)\n",
    "            if mid+1 <= qr:\n",
    "                self._update(ql, qr, val, rson, mid + 1, r)\n",
    "            self.tree[i] = (self.tree[lson] + self.tree[rson]) % MOD\n",
    "            \n",
    "    def update(self, ql, qr, val):\n",
    "        self._update(ql, qr, val, 1, 1, self.n)\n",
    "\n",
    "    def _query(self, ql, qr, i, l, r):\n",
    "        if ql <= l and r <= qr:  # 完全覆盖\n",
    "            return self.tree[i]\n",
    "        else:\n",
    "            self.pushdown(i, l, r)\n",
    "            mid = (l + r) >> 1\n",
    "            lson, rson = i<<1, i<<1|1\n",
    "            ret = 0\n",
    "            if ql <= mid:\n",
    "                ret += self._query(ql, qr, lson, l, mid)\n",
    "            if mid+1 <= qr:\n",
    "                ret += self._query(ql, qr, rson, mid + 1, r)\n",
    "            return ret % MOD\n",
    "\n",
    "    def query(self, ql, qr):\n",
    "        return self._query(ql, qr, 1, 1, self.n)\n",
    "\n",
    "    def pushdown(self, i, l, r):\n",
    "        tag = self.lazy[i]\n",
    "        if tag != 0:\n",
    "            lson, rson = i<<1, (i<<1)|1\n",
    "            mid = (l + r) >> 1\n",
    "            self.lazy[lson] += tag \n",
    "            self.lazy[lson] %= MOD\n",
    "            self.tree[lson] += (mid - l + 1) * tag\n",
    "            self.tree[lson] %= MOD\n",
    "            \n",
    "            self.lazy[rson] += tag\n",
    "            self.lazy[rson] %= MOD\n",
    "            self.tree[rson] += (r - mid) * tag\n",
    "            self.tree[rson] %= MOD\n",
    "            \n",
    "            self.lazy[i] = 0\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        tree = Tree(n+1)\n",
    "        ret = 0\n",
    "        cur_add = 0\n",
    "        last = dict()\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            if x not in last:\n",
    "                left = 0\n",
    "            else:\n",
    "                left = last[x] + 1\n",
    "            last[x] = i\n",
    "\n",
    "            sumv2 = tree.query(left+1, i+1)\n",
    "            tree.update(left+1, i+1, 1)\n",
    "            cur_add += 2*sumv2 + i - left + 1\n",
    "            cur_add %= MOD\n",
    "            ret += cur_add\n",
    "            ret %= MOD\n",
    "        return ret\n",
    "\n",
    "# print(Solution().sumCounts([1,2,1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTree:\n",
    "    __slots__ = 'arr', 'tree', 'lazy'\n",
    "\n",
    "    def __init__(self, arr):\n",
    "        self.arr = arr\n",
    "        self.tree = [0] * (4 * len(arr))\n",
    "        self.lazy = [0] * (4 * len(arr))\n",
    "        self.build(1, 0, len(arr) - 1)\n",
    "\n",
    "    def build(self, node, start, end):\n",
    "        if start == end:\n",
    "            self.tree[node] = self.arr[start]\n",
    "        else:\n",
    "            mid = (start + end) // 2\n",
    "            self.build(2 * node, start, mid)\n",
    "            self.build(2 * node + 1, mid + 1, end)\n",
    "            self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]\n",
    "\n",
    "    def update(self, node, start, end, left, right, value):\n",
    "        if self.lazy[node] != 0:\n",
    "            self.tree[node] += (end - start + 1) * self.lazy[node]\n",
    "            if start != end:\n",
    "                self.lazy[2 * node] += self.lazy[node]\n",
    "                self.lazy[2 * node + 1] += self.lazy[node]\n",
    "            self.lazy[node] = 0\n",
    "\n",
    "        if start > right or end < left:\n",
    "            return\n",
    "\n",
    "        if start >= left and end <= right:\n",
    "            self.tree[node] += (end - start + 1) * value\n",
    "            if start != end:\n",
    "                self.lazy[2 * node] += value\n",
    "                self.lazy[2 * node + 1] += value\n",
    "            return\n",
    "\n",
    "        mid = (start + end) // 2\n",
    "        self.update(2 * node, start, mid, left, right, value)\n",
    "        self.update(2 * node + 1, mid + 1, end, left, right, value)\n",
    "        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]\n",
    "\n",
    "    def query(self, node, start, end, left, right):\n",
    "        if self.lazy[node] != 0:\n",
    "            self.tree[node] += (end - start + 1) * self.lazy[node]\n",
    "            if start != end:\n",
    "                self.lazy[2 * node] += self.lazy[node]\n",
    "                self.lazy[2 * node + 1] += self.lazy[node]\n",
    "            self.lazy[node] = 0\n",
    "\n",
    "        if start > right or end < left:\n",
    "            return 0\n",
    "\n",
    "        if start >= left and end <= right:\n",
    "            return self.tree[node]\n",
    "\n",
    "        mid = (start + end) // 2\n",
    "        left_sum = self.query(2 * node, start, mid, left, right)\n",
    "        right_sum = self.query(2 * node + 1, mid + 1, end, left, right)\n",
    "        return left_sum + right_sum\n",
    "\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dic = {}\n",
    "        st = SegmentTree([0] * n)\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            l = dic.get(num, -1)\n",
    "            t = st.query(1, 0, n, l + 1, i)\n",
    "            cur = (cur + t * 2 + i - l) % kmod\n",
    "            ans = (ans + cur) % kmod\n",
    "            dic[num] = i\n",
    "            st.update(1, 0, n, l + 1, i, 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Fenwick_Tree:\n",
    "    def __init__(self, Maxsize):\n",
    "        self.tr = [0] * Maxsize\n",
    "        self.size = Maxsize\n",
    "\n",
    "    def add(self, pos, val):\n",
    "        while pos < self.size:\n",
    "            self.tr[pos] += val\n",
    "            pos += pos & (-pos)\n",
    "\n",
    "    def query(self, pos):\n",
    "        res = 0\n",
    "        while pos > 0:\n",
    "            res += self.tr[pos]\n",
    "            pos -= pos & (-pos)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, a: list[int]) -> int:\n",
    "        n = len(a)\n",
    "        tr0, tr1 = Fenwick_Tree(n + 4), Fenwick_Tree(n + 4)\n",
    "\n",
    "        def update(l: int, r: int, val: int):\n",
    "            tr0.add(l, val)\n",
    "            tr1.add(l, val * l)\n",
    "            tr0.add(r + 1, -val)\n",
    "            tr1.add(r + 1, -val * (r + 1))\n",
    "\n",
    "        def query(l: int, r: int):\n",
    "            res1 = (r + 1) * tr0.query(r) - l * tr0.query(l - 1)\n",
    "            res2 = tr1.query(r) - tr1.query(l - 1)\n",
    "            return res1 - res2\n",
    "\n",
    "        s_2 = [0] * (n + 1)\n",
    "        d = dict()\n",
    "        for i, x in enumerate(a, 1):\n",
    "            last = d.get(x, 0)\n",
    "            res = query(last + 1, i)\n",
    "            gain = i - last + 2 * res\n",
    "            update(last + 1, i, 1)\n",
    "            s_2[i] = s_2[i - 1] + gain\n",
    "            d[x] = i\n",
    "        return sum(s_2) % int(1e9 + 7)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    pass\n",
    "    print(Solution.sumCounts(None, [1, 2, 1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        self.modulo = 1000000007\n",
    "        self.p_sum1 = [0] * (n * 4)\n",
    "        self.p_sum2 = [0] * (n * 4)\n",
    "        self.lazy = [0] * (n * 4)\n",
    "        last_pos = {}\n",
    "        sum_counts = 0\n",
    "        for i in range(1, n + 1):\n",
    "            pos = 0\n",
    "            if nums[i - 1] in last_pos:\n",
    "                pos = last_pos[nums[i - 1]]\n",
    "            self.update(1, 1, n, pos + 1, i)\n",
    "            last_pos[nums[i - 1]] = i\n",
    "            sum_counts = (sum_counts + self.p_sum2[1]) % self.modulo\n",
    "        return sum_counts\n",
    "\n",
    "    def update(\n",
    "        self,\n",
    "        index: int,\n",
    "        left: int,\n",
    "        right: int,\n",
    "        query_left: int,\n",
    "        query_right: int,\n",
    "    ) -> None:\n",
    "        if left >= query_left and right <= query_right:\n",
    "            self.add(index, right - left + 1, 1)\n",
    "            self.lazy[index] += 1\n",
    "        else:\n",
    "            if self.lazy[index] > 0:\n",
    "                self.push_down(index, left, right)\n",
    "            next_index = index * 2\n",
    "            mid = (left + right) // 2\n",
    "            if query_left <= mid:\n",
    "                self.update(next_index, left, mid, query_left, query_right)\n",
    "            if query_right > mid:\n",
    "                self.update(next_index + 1, mid + 1, right, query_left, query_right)\n",
    "            self.p_sum1[index] = (\n",
    "                self.p_sum1[next_index] + self.p_sum1[next_index + 1]\n",
    "            ) % self.modulo\n",
    "            self.p_sum2[index] = (\n",
    "                self.p_sum2[next_index] + self.p_sum2[next_index + 1]\n",
    "            ) % self.modulo\n",
    "\n",
    "    def push_down(self, index: int, left: int, right: int) -> None:\n",
    "        next_index = index * 2\n",
    "        mid = (left + right) // 2\n",
    "        self.lazy[next_index] += self.lazy[index]\n",
    "        self.add(next_index, mid - left + 1, self.lazy[index])\n",
    "        self.lazy[next_index + 1] += self.lazy[index]\n",
    "        self.add(next_index + 1, right - mid, self.lazy[index])\n",
    "        self.lazy[index] = 0\n",
    "\n",
    "    def add(self, index: int, length: int, delta: int) -> None:\n",
    "        self.p_sum2[index] = (\n",
    "            self.p_sum2[index] + 2 * delta * self.p_sum1[index] + delta * delta * length\n",
    "        ) % self.modulo\n",
    "        self.p_sum1[index] = (self.p_sum1[index] + delta * length) % self.modulo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        v2i = {}\n",
    "        i2li = {}\n",
    "        for i, v in enumerate(nums) :\n",
    "            i2li[i] = v2i.get(v, -1)\n",
    "            v2i[v] = i\n",
    "        \n",
    "        class SegmentTree:\n",
    "            def __init__(self, arr):\n",
    "                self.n = len(arr)\n",
    "                self.tree = [0] * (4 * self.n)\n",
    "                self.lazy = [0] * (4 * self.n)\n",
    "                self.build_tree(arr, 0, self.n-1)\n",
    "\n",
    "            # 构建线段树，2n个节点。非叶子节点的tree值储存的是子树和。\n",
    "            def build_tree(self, arr, l, r, idx=1):\n",
    "                if l == r:\n",
    "                    self.tree[idx] = arr[l]\n",
    "                    return\n",
    "                mid = (l + r) // 2\n",
    "                self.build_tree(arr, l, mid, idx*2)\n",
    "                self.build_tree(arr, mid+1, r, idx*2+1)\n",
    "                self.tree[idx] = self.tree[idx*2] + self.tree[idx*2+1]\n",
    "\n",
    "            # 内部调用处理懒更新的函数\n",
    "            def push_down(self, l, r, idx):\n",
    "                if self.lazy[idx]:\n",
    "                    mid = (l + r) // 2\n",
    "                    self.tree[idx*2] += self.lazy[idx] * (mid - l + 1)\n",
    "                    self.tree[idx*2+1] += self.lazy[idx] * (r - mid)\n",
    "                    self.lazy[idx*2] += self.lazy[idx]\n",
    "                    self.lazy[idx*2+1] += self.lazy[idx]\n",
    "                    self.lazy[idx] = 0\n",
    "\n",
    "            # [ql, qr]区间都加上val\n",
    "            def update(self, ql, qr, val, l=0, r=None, idx=1):\n",
    "                if r is None:\n",
    "                    r = self.n-1\n",
    "\n",
    "                if ql <= l and qr >= r:\n",
    "                    self.tree[idx] += val * (r - l + 1)\n",
    "                    self.lazy[idx] += val\n",
    "                    return\n",
    "                self.push_down(l, r, idx)\n",
    "                mid = (l + r) // 2\n",
    "                if ql <= mid:\n",
    "                    self.update(ql, qr, val, l, mid, idx*2)\n",
    "                if qr > mid:\n",
    "                    self.update(ql, qr, val, mid+1, r, idx*2+1)\n",
    "                self.tree[idx] = self.tree[idx*2] + self.tree[idx*2+1]\n",
    "\n",
    "            # 计算[ql, qr]区间的和\n",
    "            def query(self, ql, qr, l=0, r=None, idx=1):\n",
    "                if qr < ql :\n",
    "                    return 0\n",
    "\n",
    "                if r is None:\n",
    "                    r = self.n-1\n",
    "\n",
    "                if ql <= l and qr >= r:\n",
    "                    return self.tree[idx]\n",
    "                self.push_down(l, r, idx)\n",
    "                mid = (l + r) // 2\n",
    "                res = 0\n",
    "                if ql <= mid:\n",
    "                    res += self.query(ql, qr, l, mid, idx*2)\n",
    "                if qr > mid:\n",
    "                    res += self.query(ql, qr, mid+1, r, idx*2+1)\n",
    "                return res\n",
    "        \n",
    "        tree = SegmentTree([0]*len(nums))\n",
    "        temp_v = 0\n",
    "        to_ret = 0\n",
    "        for i, v in enumerate(nums) :\n",
    "            p_start = i2li[i]\n",
    "            temp_v += 2*tree.query(p_start+1, i-1) + (i-p_start-1) + 1\n",
    "            tree.update(p_start+1, i, 1)\n",
    "            to_ret += temp_v\n",
    "        return to_ret % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n: int):\n",
    "        self.size = n\n",
    "        self._tree1 = defaultdict(int)\n",
    "        self._tree2 = defaultdict(int)\n",
    "\n",
    "    @staticmethod\n",
    "    def _lowbit(index: int) -> int:\n",
    "        return index & -index\n",
    "\n",
    "    def add(self, left: int, right: int, delta: int) -> None:\n",
    "        self._add(left, delta)\n",
    "        self._add(right + 1, -delta)\n",
    "\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self._query(right) - self._query(left - 1)\n",
    "\n",
    "    def _add(self, index: int, delta: int) -> None:\n",
    "        if index <= 0:\n",
    "            raise ValueError('index 必须是正整数')\n",
    "\n",
    "        rawIndex = index\n",
    "        while index <= self.size:\n",
    "            self._tree1[index] += delta\n",
    "            self._tree2[index] += (rawIndex - 1) * delta\n",
    "            index += self._lowbit(index)\n",
    "\n",
    "    def _query(self, index: int) -> int:\n",
    "        if index > self.size:\n",
    "            index = self.size\n",
    "\n",
    "        rawIndex = index\n",
    "        res = 0\n",
    "        while index > 0:\n",
    "            res += rawIndex * self._tree1[index] - self._tree2[index]\n",
    "            index -= self._lowbit(index)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, A: List[int]) -> int:\n",
    "        last = {}\n",
    "        bit = BIT(len(A))\n",
    "        res = cur = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        for r,a in enumerate(A):\n",
    "            l = last.get(a, -1) + 1\n",
    "            v = bit.query(l + 1, r + 1)\n",
    "            bit.add(l + 1, r + 1, 1)\n",
    "            cur += 2 * v + (r - l + 1)\n",
    "            res = (res + cur) % mod\n",
    "            last[a] = r\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10**9 + 7\n",
    "class segTree:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.s = [0]*(4*n)\n",
    "        self.lazy = [0]*(4*n)\n",
    "    def push_up(self, p):\n",
    "        self.s[p] = self.s[p*2] + self.s[p*2 + 1]\n",
    "    def push_down(self, st, end, p):\n",
    "        mid = (st + end)>>1\n",
    "        self.s[p*2] += self.lazy[p]*(mid - st + 1)\n",
    "        self.s[p*2 + 1] += self.lazy[p]*(end - mid)\n",
    "        self.lazy[p*2] += self.lazy[p]\n",
    "        self.lazy[p*2 + 1] += self.lazy[p]\n",
    "        self.lazy[p] = 0    \n",
    "    def update(self, l, r, val, st, end, p):\n",
    "        if r<l:\n",
    "            return \n",
    "        if r<st or l>end:\n",
    "            return \n",
    "        if l<=st and r>=end:\n",
    "            self.s[p] += (end - st + 1)*val \n",
    "            self.lazy[p] += val \n",
    "            return \n",
    "        if (st!=end) and (self.lazy[p]!=0):\n",
    "            self.push_down(st, end, p)\n",
    "        mid = (st + end)>>1\n",
    "        if l<=mid:\n",
    "            self.update(l, r, val, st, mid, p*2)\n",
    "        if r>mid:\n",
    "            self.update(l, r, val, mid+1, end, p*2 + 1)\n",
    "        self.push_up(p)\n",
    "    def find(self, l, r, st, end, p):\n",
    "        if r<l:\n",
    "            return 0\n",
    "        if (r<st) or (l>end):\n",
    "            return 0 \n",
    "        if l<=st and r>=end:\n",
    "            return self.s[p] \n",
    "        if (st!=end) and (self.lazy[p]!=0):\n",
    "            self.push_down(st, end, p)\n",
    "        mid = (st + end)>>1\n",
    "        ans = 0\n",
    "        if l<=mid:\n",
    "            ans += self.find(l, r, st, mid, p*2)\n",
    "        if r>mid:\n",
    "            ans += self.find(l, r, mid+1, end, p*2 + 1)\n",
    "        return ans \n",
    "class Solution:\n",
    "    def sumCounts(self, a: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        s = {j:-1 for j in range(n)}\n",
    "        dic = {}\n",
    "        for j in range(len(a)):\n",
    "            if a[j] in dic:\n",
    "                s[j] = dic[a[j]] \n",
    "            dic[a[j]] = j \n",
    "        b = segTree(n)\n",
    "        ans = 0 \n",
    "        tmp = 0 \n",
    "        for j in range(n):\n",
    "            left = s[j]\n",
    "            tmp += (j-1-left) + 1 + 2*b.find(left+1, j-1, 0, n-1, 1)\n",
    "            tmp %= mod \n",
    "            # print(tmp)\n",
    "            ans += tmp \n",
    "            b.update(left+1, j, 1, 0, n-1, 1)\n",
    "        return ans%(10**9 + 7) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTreeRangeModifyAdd:\n",
    "    \"\"\"线段树区间修改, 区间求和, 可以用树状数组平替\n",
    "    需要用到lazy tag\n",
    "    lazy tag: 用一个数组维护每个区间需要更新的值\n",
    "    如果这个值 = 0, 表示不需要更新\n",
    "    如果这个值 != 0, 表示更新操作在这个区间停住了, 不继续递归更新子区间了\n",
    "    如果后面又来了一个更新破坏了lazy tag的区间, 那就得继续更新\n",
    "    #! 当添加懒标记的时候对当前区间进行更新, 但是不对子区间进行更新\n",
    "    #! 不一定用0来做判断, 但是对于求和来说是0\n",
    "    \n",
    "    \"\"\"\n",
    "    def __init__(self, n: int, nums: List[int]) -> None:\n",
    "        \"\"\"初始化线段树类\n",
    "\n",
    "        Args:\n",
    "            n (int): 初始数组的长度\n",
    "            nums (List[int]): 初始的数组\n",
    "        \"\"\"\n",
    "        self.sm = [0] * (n*4)\n",
    "        self.nums = nums\n",
    "        self.build(1, 1, n)\n",
    "        self.todo = [0] * (n*4) #! 存储区间更新是否停住了, 其他情况不一定是1(比如如果是区间乘, 就应该设置成1)\n",
    "        \n",
    "    def maintain(self, o: int)->None:\n",
    "        \"\"\"更新完左右子树后对当前节点进行维护\n",
    "\n",
    "        Args:\n",
    "            o (int): 当前的节点编号\n",
    "        \"\"\"\n",
    "        self.sm[o] = self.sm[o*2] + self.sm[o*2+1]\n",
    "        \n",
    "    def build(self, o: int, l: int, r: int)->None:\n",
    "        \"\"\"构建[l, r]内的线段树\n",
    "\n",
    "        Args:\n",
    "            o (int): 当前的节点编号\n",
    "            l (int): 要构建的区间的左端点\n",
    "            r (int): 要构建的区间的右端点\n",
    "        \"\"\"\n",
    "        if l == r:  #* 如果左右端点相等, 说明是叶子节点, 直接赋值即可\n",
    "            #* 因为l的范围是[1, n], 所以作为数组的索引时需要减一\n",
    "            self.sm[o] = self.nums[l-1]\n",
    "            return\n",
    "        \n",
    "        #* 否则需要递归遍历左右子树\n",
    "        mid = (l+r)//2\n",
    "        self.build(o*2, l, mid)\n",
    "        self.build(o*2+1, mid+1, r)\n",
    "        self.maintain(o)\n",
    "        \n",
    "    #* 具体操作就是add[1, 1, n, idx, val, add], 前面三个参数是不变的\n",
    "    def update(self, o: int, l: int, r: int, L: int, R: int, add: int)->None:\n",
    "        \"\"\"在[L, R]区间都加上add\n",
    "        #! 需要注意的是idx的范围是[1, n]并不是从0开始\n",
    "\n",
    "        Args:\n",
    "            o (int): 当前的节点编号\n",
    "            l (int): 当前的节点所对应的区间左端点\n",
    "            r (int): 当前的节点所对应的区间右端点\n",
    "            L (int): 需要增加的区间的左端点\n",
    "            R (int): 需要增加的区间的右端点\n",
    "            add (int): 需要增加的数\n",
    "        \"\"\"\n",
    "        if L <= l and r <= R:\n",
    "            self.todo[o] += add  #* 不再继续递归更新了\n",
    "            self.sm[o] += (r-l+1)*add\n",
    "            return\n",
    "        \n",
    "        mid = (l+r)//2\n",
    "        \n",
    "        self.do(o, l, r)\n",
    "        if mid>=L: self.update(o*2, l, mid, L, R, add)\n",
    "        if mid < R: self.update(o*2+1, mid+1, r, L, R, add)\n",
    "        self.maintain(o)\n",
    "        \n",
    "    def do(self, o: int, l: int, r: int):\n",
    "        \"\"\"将值传给子节点\n",
    "        #! 其他的代码需要更新这个\n",
    "\n",
    "        Args:\n",
    "            o (int): 子节点的编号\n",
    "            l (int): 当前节点所代表的区间的左端点\n",
    "            r (int): 当前节点所代表的区间的右端点\n",
    "        \"\"\"\n",
    "        mid = (l+r)//2\n",
    "        if l!=r and self.todo[o] != 0:  #* 如果不是叶子节点并且有懒标记 \n",
    "            #* 传给左右儿子\n",
    "            self.todo[o*2] += self.todo[o]\n",
    "            self.todo[o*2+1] += self.todo[o]\n",
    "            self.sm[o*2] += (mid-l+1) * self.todo[o]\n",
    "            self.sm[o*2+1] += (r-mid) * self.todo[o]\n",
    "            #* 自身清空\n",
    "            self.todo[o] = 0\n",
    "    \n",
    "    #* 具体操作就是query_sum[1, 1, n, L ,R], 前面三个参数是不变的\n",
    "    def query_sum(self, o: int, l: int ,r: int, L: int, R: int)->int:\n",
    "        \"\"\"求[L, R]的区间和\n",
    "\n",
    "        Args:\n",
    "            o (int): 当前的节点编号\n",
    "            l (int): 当前节点所对应的区间的左端点\n",
    "            r (int): 当前节点所对应的区间的右端点\n",
    "            L (int): 查询的区间的左端点\n",
    "            R (int): 查询的区间的右端点\n",
    "\n",
    "        Returns:\n",
    "            int: 区间和\n",
    "        \"\"\"\n",
    "        if L<=l and R>=r:\n",
    "            return self.sm[o]\n",
    "\n",
    "        sm = 0\n",
    "        self.do(o, l, r)\n",
    "        mid = (l+r)//2\n",
    "        if(L <= mid):\n",
    "            sm += self.query_sum(o*2, l, mid, L, R)\n",
    "        if(R > mid):\n",
    "            sm += self.query_sum(o*2+1, mid+1, r, L, R)\n",
    "        return sm\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        #* 记录位置\n",
    "        pos = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            pos[num].append(i)\n",
    "        #* dp[i]表示以第i个字符为结尾的子数组的平方和\n",
    "        #* dp1[i]表示第i个字符为记为的子数组的和\n",
    "        dp = [1] * n\n",
    "        \n",
    "        st = SegmentTreeRangeModifyAdd(n, [1] + [0] * (n-1))\n",
    "        MOD = 10**9+7\n",
    "        for i in range(1, n):\n",
    "            num = nums[i]\n",
    "            #* 说明是第一次遇到\n",
    "            if pos[num][0]==i:\n",
    "                dp[i] = (dp[i-1]+2*st.query_sum(1, 1, n, 1, i) + i+1) % MOD\n",
    "                st.update(1, 1, n, 1, i+1, 1)\n",
    "            else:\n",
    "                idx = bisect_left(pos[num], i)\n",
    "                dp[i] = (dp[i-1]+2*st.query_sum(1, 1, n, pos[num][idx-1]+2, i) + (i-pos[num][idx-1])) % MOD\n",
    "                \n",
    "                st.update(1, 1, n, pos[num][idx-1]+2, i+1, 1)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = (ans+dp[i])%MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "    \"\"\"线段树\n",
    "    Application:\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, lt, m=-1):\n",
    "        self._n = len(lt)\n",
    "        self._m = m\n",
    "        self._sum = [0] * (4 * self._n + 1)\n",
    "        self._add = [0] * (4 * self._n + 1)\n",
    "\n",
    "        def init(k, p, q):\n",
    "            if p == q:\n",
    "                self._sum[k] = lt[p]\n",
    "                if self._m != -1:\n",
    "                    self._sum[k] %= self._m\n",
    "                return\n",
    "            m = (p + q) >> 1\n",
    "            init(k << 1, p, m)\n",
    "            init((k << 1) + 1, m + 1, q)\n",
    "            self._sum[k] = self._sum[k << 1] + self._sum[(k << 1) + 1]\n",
    "            if self._m != -1:\n",
    "                self._sum[k] %= self._m\n",
    "\n",
    "        init(1, 0, self._n - 1)\n",
    "\n",
    "    def range_add(self, u, v, val):\n",
    "        def dfs(k, p, q, u, v, s):\n",
    "            if p == u and q == v:\n",
    "                ans = self._sum[k] + s * (v - u + 1)\n",
    "                ans %= self._m\n",
    "                self._sum[k] += val * (v - u + 1)\n",
    "                if self._m != -1:\n",
    "                    self._sum[k] %= self._m\n",
    "                self._add[k] += val\n",
    "                if self._m != -1:\n",
    "                    self._add[k] %= self._m\n",
    "                return ans\n",
    "            m = (p + q) >> 1\n",
    "            s += self._add[k]\n",
    "            s %= self._m\n",
    "            ans = 0\n",
    "            if u <= m:\n",
    "                ans += dfs(k << 1, p, m, u, min(m, v), s)\n",
    "            if v > m:\n",
    "                ans += dfs((k << 1) + 1, m + 1, q, max(m + 1, u), v, s)\n",
    "            self._sum[k] = (\n",
    "                self._sum[k << 1] + self._sum[(k << 1) + 1] + self._add[k] * (q - p + 1)\n",
    "            )\n",
    "            if self._m != -1:\n",
    "                self._sum[k] %= self._m\n",
    "            ans %= self._m\n",
    "            return ans\n",
    "\n",
    "        return dfs(1, 0, self._n - 1, u, v, 0)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums):\n",
    "        n = len(nums)\n",
    "        M = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        t = 0\n",
    "        p = [-1] * 100001\n",
    "        st = SegmentTree([0] * n, M)\n",
    "        \n",
    "        for i in range(n):\n",
    "            t = (t + st.range_add(p[nums[i]] + 1 ,i, 1) * 2 + i - p[nums[i]]) % M\n",
    "            ans = (ans + t) % M\n",
    "            p[nums[i]] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import *\n",
    "from re import *\n",
    "from datetime import *\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from bisect import *\n",
    "from copy import *\n",
    "from math import *\n",
    "from random import *\n",
    "from statistics import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from operator import *\n",
    "from io import *\n",
    "from sys import *\n",
    "from json import *\n",
    "from builtins import *\n",
    "from typing import *\n",
    "\n",
    "\"\"\"\n",
    "You are given a 0-indexed integer array nums.\n",
    "\n",
    "The distinct count of a subarray of nums is defined as:\n",
    "\n",
    " * Let nums[i..j] be a subarray of nums consisting of all the indices from i to j such that 0 <= i\n",
    "   <= j < nums.length. Then the number of distinct values in nums[i..j] is called the distinct count\n",
    "   of nums[i..j].\n",
    "\n",
    "Return the sum of the squares of distinct counts of all subarrays of nums.\n",
    "\n",
    "Since the answer may be very large, return it modulo 109 + 7.\n",
    "\n",
    "A subarray is a contiguous non-empty sequence of elements within an array.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "\n",
    "Input: nums = [1,2,1]\n",
    "Output: 15\n",
    "Explanation: Six possible subarrays are:\n",
    "[1]: 1 distinct value\n",
    "[2]: 1 distinct value\n",
    "[1]: 1 distinct value\n",
    "[1,2]: 2 distinct values\n",
    "[2,1]: 2 distinct values\n",
    "[1,2,1]: 2 distinct values\n",
    "The sum of the squares of the distinct counts in all subarrays is equal to 12 + 12 + 12 + 22 + 22 + 22 = 15.\n",
    "\n",
    "\n",
    "Example 2:\n",
    "\n",
    "\n",
    "Input: nums = [2,2]\n",
    "Output: 3\n",
    "Explanation: Three possible subarrays are:\n",
    "[2]: 1 distinct value\n",
    "[2]: 1 distinct value\n",
    "[2,2]: 1 distinct value\n",
    "The sum of the squares of the distinct counts in all subarrays is equal to 12 + 12 + 12 = 3.\n",
    "\n",
    " \n",
    "\n",
    "Constraints:\n",
    "\n",
    " * 1 <= nums.length <= 105\n",
    " * 1 <= nums[i] <= 105\n",
    "\"\"\"\n",
    "\n",
    "MOD = 1000000007 # 998244353\n",
    "\n",
    "class LazySegmentTree():\n",
    "    __slots__ = ['n', 'log', 'size', 'd', 'lz', 'e', 'op', 'mapping', 'composition', 'identity']\n",
    "    def _update(self, k):self.d[k]=self.op(self.d[2 * k], self.d[2 * k + 1])\n",
    "    def _all_apply(self, k, f):\n",
    "        self.d[k]=self.mapping(f,self.d[k])\n",
    "        if (k<self.size):self.lz[k]=self.composition(f,self.lz[k])\n",
    "    def _push(self, k):\n",
    "        if self.lz[k] == self.identity: return\n",
    "        self._all_apply(2 * k, self.lz[k])\n",
    "        self._all_apply(2 * k + 1, self.lz[k])\n",
    "        self.lz[k]=self.identity\n",
    "    def __init__(self,V,OP,E,MAPPING,COMPOSITION,ID):\n",
    "        self.n=len(V)\n",
    "        self.log=(self.n-1).bit_length()\n",
    "        self.size=1<<self.log\n",
    "        self.d=[E for i in range(2*self.size)]\n",
    "        self.lz=[ID for i in range(self.size)]\n",
    "        self.e=E\n",
    "        self.op=OP\n",
    "        self.mapping=MAPPING\n",
    "        self.composition=COMPOSITION\n",
    "        self.identity=ID\n",
    "        for i in range(self.n):self.d[self.size+i]=V[i]\n",
    "        for i in range(self.size-1,0,-1):self._update(i)\n",
    "    def set(self,p,x):\n",
    "        assert 0<=p and p<self.n\n",
    "        p+=self.size\n",
    "        for i in range(self.log,0,-1):self._push(p >> i)\n",
    "        self.d[p]=x\n",
    "        for i in range(1,self.log+1):self._update(p >> i)\n",
    "    def get(self,p):\n",
    "        assert 0<=p and p<self.n\n",
    "        p+=self.size\n",
    "        for i in range(self.log,0,-1):self._push(p >> i)\n",
    "        return self.d[p]\n",
    "    def prod(self,l,r):\n",
    "        assert 0<=l and l<=r and r<=self.n\n",
    "        if l==r:return self.e\n",
    "        l+=self.size\n",
    "        r+=self.size\n",
    "        for i in range(self.log,0,-1):\n",
    "            if (((l>>i)<<i)!=l):self._push(l >> i)\n",
    "            if (((r>>i)<<i)!=r):self._push(r >> i)\n",
    "        sml,smr=self.e,self.e\n",
    "        while(l<r):\n",
    "            if l&1:\n",
    "                sml=self.op(sml,self.d[l])\n",
    "                l+=1\n",
    "            if r&1:\n",
    "                r-=1\n",
    "                smr=self.op(self.d[r],smr)\n",
    "            l>>=1\n",
    "            r>>=1\n",
    "        return self.op(sml,smr)\n",
    "    def all_prod(self):return self.d[1]\n",
    "    def apply_point(self,p,f):\n",
    "        assert 0<=p and p<self.n\n",
    "        p+=self.size\n",
    "        for i in range(self.log,0,-1):self._push(p >> i)\n",
    "        self.d[p]=self.mapping(f,self.d[p])\n",
    "        for i in range(1,self.log+1):self._update(p >> i)\n",
    "    def apply(self,l,r,f):\n",
    "        assert 0<=l and l<=r and r<=self.n\n",
    "        if l==r:return\n",
    "        l+=self.size\n",
    "        r+=self.size\n",
    "        for i in range(self.log,0,-1):\n",
    "            if (((l>>i)<<i)!=l):self._push(l >> i)\n",
    "            if (((r>>i)<<i)!=r):self._push((r - 1) >> i)\n",
    "        l2,r2=l,r\n",
    "        while(l<r):\n",
    "            if (l&1):\n",
    "                self._all_apply(l, f)\n",
    "                l+=1\n",
    "            if (r&1):\n",
    "                r-=1\n",
    "                self._all_apply(r, f)\n",
    "            l>>=1\n",
    "            r>>=1\n",
    "        l,r=l2,r2\n",
    "        for i in range(1,self.log+1):\n",
    "            if (((l>>i)<<i)!=l):self._update(l >> i)\n",
    "            if (((r>>i)<<i)!=r):self._update((r - 1) >> i)\n",
    "    def max_right(self,l,g):\n",
    "        assert 0<=l and l<=self.n\n",
    "        assert g(self.e)\n",
    "        if l==self.n:return self.n\n",
    "        l+=self.size\n",
    "        for i in range(self.log,0,-1):self._push(l >> i)\n",
    "        sm=self.e\n",
    "        while(1):\n",
    "            while(i%2==0):l>>=1\n",
    "            if not(g(self.op(sm,self.d[l]))):\n",
    "                while(l<self.size):\n",
    "                    self._push(l)\n",
    "                    l=(2*l)\n",
    "                    if (g(self.op(sm,self.d[l]))):\n",
    "                        sm=self.op(sm,self.d[l])\n",
    "                        l+=1\n",
    "                return l-self.size\n",
    "            sm=self.op(sm,self.d[l])\n",
    "            l+=1\n",
    "            if (l&-l)==l:break\n",
    "        return self.n\n",
    "    def min_left(self,r,g):\n",
    "        assert (0<=r and r<=self.n)\n",
    "        assert g(self.e)\n",
    "        if r==0:return 0\n",
    "        r+=self.size\n",
    "        for i in range(self.log,0,-1):self._push((r - 1) >> i)\n",
    "        sm=self.e\n",
    "        while(1):\n",
    "            r-=1\n",
    "            while(r>1 and (r%2)):r>>=1\n",
    "            if not(g(self.op(self.d[r],sm))):\n",
    "                while(r<self.size):\n",
    "                    self._push(r)\n",
    "                    r=(2*r+1)\n",
    "                    if g(self.op(self.d[r],sm)):\n",
    "                        sm=self.op(self.d[r],sm)\n",
    "                        r-=1\n",
    "                return r+1-self.size\n",
    "            sm=self.op(self.d[r],sm)\n",
    "            if (r&-r)==r:break\n",
    "        return 0\n",
    "\n",
    "def OP(A, B):\n",
    "    return [(A[0] + B[0]) % MOD, (A[1] + B[1]) % MOD, A[2] + B[2]]\n",
    "\n",
    "E = [0, 0, 0]\n",
    "\n",
    "def MAPP(fn, A):\n",
    "    x2, x, c = A\n",
    "    return [(x2 + c * fn * fn + 2 * fn * x) % MOD, (x + c * fn) % MOD, c]\n",
    "\n",
    "ID = 0\n",
    "\n",
    "def COMP(fn, gn):\n",
    "    return fn + gn\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        book = [-1] * (max(nums) + 1)\n",
    "        res = 0\n",
    "        lst = LazySegmentTree([[0, 0, 1] for x in nums],\n",
    "                              OP, E, MAPP, COMP, ID)\n",
    "\n",
    "        for right, x in enumerate(nums):\n",
    "            left = book[x] + 1\n",
    "\n",
    "            lst.apply(left, right + 1, 1)\n",
    "            # print(left, right, lst.all_prod())\n",
    "            res = (res + lst.all_prod()[0]) % MOD\n",
    "                \n",
    "            book[x] = right\n",
    "        \n",
    "        return res % MOD\n",
    "\n",
    "testcases = [\n",
    "    # [[2, 2, 5, 5]],\n",
    "    # [],\n",
    "]\n",
    "\n",
    "s = Solution()\n",
    "func_name = dir(s)[-1]\n",
    "func = getattr(s, func_name)\n",
    "\n",
    "for args in testcases:\n",
    "    print(func(*args))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.tre,self.tag=[0]*262150,[0]*262150\n",
    "        self.f=[0]*100050\n",
    "    def mktree(self,now,ls,rs):\n",
    "        if(ls==rs):self.tre[now]=(self.f[ls-1]*self.f[ls-1],self.f[ls-1]);return\n",
    "        noww,nrs=now<<1,(ls+rs)>>1\n",
    "        self.mktree(noww,ls,nrs);self.mktree(noww|1,nrs+1,rs)\n",
    "        self.tre[now]=(self.tre[noww][0]+self.tre[noww|1][0],self.tre[noww][1]+self.tre[noww|1][1])\n",
    "    def pushtag(self,now,ls,rs):\n",
    "        noww,nrs=now<<1,(ls+rs)>>1\n",
    "        self.tre[noww]=(self.tre[noww][0]-2*self.tag[now]*self.tre[noww][1]+self.tag[now]*self.tag[now]*(nrs-ls+1),self.tre[noww][1]-self.tag[now]*(nrs-ls+1))\n",
    "        self.tre[noww|1]=(self.tre[noww|1][0]-2*self.tag[now]*self.tre[noww|1][1]+self.tag[now]*self.tag[now]*(rs-nrs),self.tre[noww|1][1]-self.tag[now]*(rs-nrs))\n",
    "        self.tag[noww]+=self.tag[now];self.tag[noww|1]+=self.tag[now];self.tag[now]=0\n",
    "    def change(self,now,ls,rs,l,r):\n",
    "        if(l>rs or r<ls):return\n",
    "        if(l<=ls and rs<=r):\n",
    "            self.tre[now]=(self.tre[now][0]-2*self.tre[now][1]+rs-ls+1,self.tre[now][1]-rs+ls-1)\n",
    "            self.tag[now]+=1;return\n",
    "        if(self.tag[now]):self.pushtag(now,ls,rs)\n",
    "        noww,nrs=now<<1,(ls+rs)>>1\n",
    "        self.change(noww,ls,nrs,l,r);self.change(noww|1,nrs+1,rs,l,r)\n",
    "        self.tre[now]=(self.tre[noww][0]+self.tre[noww|1][0],self.tre[noww][1]+self.tre[noww|1][1])\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n,mp=len(nums),{}\n",
    "        net=[n]*n\n",
    "        for i in range(n):\n",
    "            if(nums[i] not in mp):mp[nums[i]]=i\n",
    "            else:net[mp[nums[i]]]=i;mp[nums[i]]=i\n",
    "        mp,x,ans={},0,0\n",
    "        for i in range(n):\n",
    "            if(nums[i] not in mp):mp[nums[i]]=1;x+=1\n",
    "            else:mp[nums[i]]+=1\n",
    "            self.f[i]=x;ans+=x*x\n",
    "        self.mktree(1,1,n)\n",
    "        for i in range(n):\n",
    "            self.change(1,1,n,i+1,net[i])\n",
    "            ans+=self.tre[1][0]\n",
    "        return ans%1000000007\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "1. 以 i 为右端点来处理所有的子数组，假设 i 和前面的都不重复，那么对比 i-1 为右端点，新增了多少？\n",
    "假设 i-1 为右端点有 3 个数：1^2 + 2^2 + 3^3，那么 i为右端点：1^2 + 2^2 + 3^3 + 4^2，相减得：4^2-3^2 + 3^2-2^2 + 2^2 - 1^2 + 1^2 + 0^2 = 2*(3+2+1+0) + 4\n",
    "    推广一下 ==> (x1+1)^2 - x1^2 + (x2+1)^2 - x2^2 + (x3+1)^2 - x3^2 = 2*x1 + 1 + 2*x2 + 1 + 2*x3 + 1 = 2*(x1+x2+x3) + 3 -> 其实就是多了两倍的累加和\n",
    "2. 如果 [0,i-1] 有一个距离 i 最近的下标 j，和 i 是一样的值，那么新增了多少？\n",
    "增加了：2*(1+2+..+ i-j-1) + i-j, 需要记录每个值最后出现的位置\n",
    "\"\"\"\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.add = 0\n",
    "        self.sum = 0\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        node = Node()\n",
    "        l, r = 1, n\n",
    "        # 为了方便，没有出现过为 0，下标从 1 开始计算, \n",
    "        last = defaultdict(int)\n",
    "        total = s = 0\n",
    "        for i, v in enumerate(nums, 1):\n",
    "            j = last.get(v, 0)\n",
    "            # 查询是区间 [j+1, i] 有多少个不同的值，然后更新 [j+1, i] 加一个数 => 多了一个不同的数\n",
    "            val = self.query(node, j + 1, i, l, r)\n",
    "            s += 2 * val + i - j\n",
    "            print(i, j, val, s)\n",
    "            self.update(node, j + 1, i, l, r)\n",
    "            total = (total + s) % mod\n",
    "            last[v] = i\n",
    "        return total\n",
    "    def query(self, node: Node, L: int, R: int, l: int, r: int) -> int:\n",
    "        if L <= l and r <= R:\n",
    "            \n",
    "            return node.sum\n",
    "        mid = (l + r) // 2\n",
    "        self.build(node, l, mid, r)\n",
    "        ans = 0\n",
    "        if L <= mid:\n",
    "            ans += self.query(node.left, L, R, l, mid)\n",
    "        if R > mid:\n",
    "            ans += self.query(node.right, L, R, mid + 1, r)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "    def update(self, node: Node, L: int, R: int, l: int, r: int) -> None:\n",
    "        if L <= l and r <= R:\n",
    "            node.add += 1\n",
    "            node.sum += r - l + 1\n",
    "            return\n",
    "        mid = (l + r) >> 1\n",
    "        self.build(node, l, mid, r)\n",
    "        if L <= mid:\n",
    "            self.update(node.left, L, R, l, mid)\n",
    "        if R > mid:\n",
    "            self.update(node.right, L, R, mid + 1, r)\n",
    "        node.sum = node.left.sum + node.right.sum\n",
    "\n",
    "    def build(self, node: Node, l: int, mid: int, r: int) -> None:\n",
    "        if node.left is None:\n",
    "            node.left = Node()\n",
    "        if node.right is None:\n",
    "            node.right = Node()\n",
    "        if node.add == 0:\n",
    "            return\n",
    "        node.left.add += node.add\n",
    "        node.right.add += node.add\n",
    "        node.left.sum += node.add * (mid - l + 1)\n",
    "        node.right.sum += node.add * (r - mid)\n",
    "        node.add = 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slot__ = 'val', 'left', 'right', 'lazy', 'max'\n",
    "    def __init__(self, val=0, lazy=0, left=None, right=None) -> None:\n",
    "        self.val = val \n",
    "        self.left = left \n",
    "        self.right = right \n",
    "        self.lazy = lazy\n",
    "\n",
    "\n",
    "class SegTree:\n",
    "    __slot__ = 'root', 'start', 'end'\n",
    "    def __init__(self, val=0, start=-10**9, end=10**9 ) -> None:\n",
    "        self.root = Node(val=val)\n",
    "        self.start = start\n",
    "        self.end = end \n",
    "      \n",
    "\n",
    "    def update(self, l, r, val):\n",
    "        def _update(start=self.start, end=self.end, node=self.root):\n",
    "            if l <= start and end <= r:\n",
    "                node.val += (end - start + 1) * val\n",
    "                node.lazy += val\n",
    "                return \n",
    "            \n",
    "            mid = math.floor((start + end) / 2)\n",
    "            self.pushDown(node, mid - start + 1, end - mid)\n",
    "            if l <= mid:\n",
    "                _update(start, mid, node.left)\n",
    "            if r > mid:\n",
    "                _update(mid + 1, end, node.right)\n",
    "            self.pushUp(node)\n",
    "        _update()\n",
    "        \n",
    "\n",
    "    def query(self, l, r):\n",
    "        def _query(node=self.root, start=self.start, end=self.end): #max\n",
    "            if l <= start and end <= r:\n",
    "                t = node.val\n",
    "                node.val += (end - start + 1)\n",
    "                node.lazy += 1\n",
    "                return t\n",
    "            mid = math.floor((start + end) / 2) \n",
    "            ans = 0\n",
    "            self.pushDown(node, mid - start + 1, end - mid)\n",
    "            if l <= mid: \n",
    "                ans += _query(node.left, start, mid)\n",
    "            if r > mid: \n",
    "                ans += _query(node.right, mid + 1, end)\n",
    "            self.pushUp(node)\n",
    "            return ans \n",
    "\n",
    "        return _query()\n",
    "    \n",
    "\n",
    "    def pushDown(self, node, leftNum, rightNum):\n",
    "        if node.left == None:\n",
    "            node.left = Node()\n",
    "        if node.right == None: \n",
    "            node.right = Node()\n",
    "        if node.lazy == 0:\n",
    "            return\n",
    "        node.left.val += node.lazy * leftNum\n",
    "        node.right.val += node.lazy * rightNum\n",
    "        # 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖\n",
    "        node.left.lazy += node.lazy\n",
    "        node.right.lazy += node.lazy\n",
    "        node.lazy = 0\n",
    "\n",
    "    def pushUp(self, node):\n",
    "        node.val = node.left.val + node.right.val\n",
    "\n",
    "            \n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        seg = SegTree(0, -1, nums.__len__()-1)\n",
    "        last = defaultdict(lambda: -1)\n",
    "        sum = 0 \n",
    "        cur_sum = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            last_i = last[v]\n",
    "            cur_sum += 2*seg.query(last_i+1, i) + i - last_i\n",
    "            sum += cur_sum % (10**9+7)\n",
    "            # seg.update(last_i+1, i, 1)\n",
    "            last[v] = i\n",
    "            \n",
    "        return sum % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        sums=[0]*(n*4)\n",
    "        lazy=[0]*(n*4)\n",
    "        def query(o,l,r,L,R):\n",
    "            if L<=l and r<=R:\n",
    "                return sums[o]\n",
    "            m=(l+r)//2\n",
    "            if lazy[o]:\n",
    "                sums[o*2]+=lazy[o]*(m-l+1)\n",
    "                sums[o*2+1]+=lazy[o]*(r-m)\n",
    "                lazy[o*2]+=lazy[o]\n",
    "                lazy[o*2+1]+=lazy[o]\n",
    "                lazy[o]=0\n",
    "            res=0\n",
    "            if L<=m:res+=query(o*2,l,m,L,R)\n",
    "            if m<R:res+=query(o*2+1,m+1,r,L,R)\n",
    "            return res\n",
    "        def addone(o,l,r,L,R):\n",
    "            if L<=l and r<=R:\n",
    "                sums[o]+=(r-l+1)\n",
    "                lazy[o]+=1\n",
    "                return\n",
    "            m=(l+r)//2\n",
    "            if lazy[o]:\n",
    "                sums[o*2]+=lazy[o]*(m-l+1)\n",
    "                sums[o*2+1]+=lazy[o]*(r-m)\n",
    "                lazy[o*2]+=lazy[o]\n",
    "                lazy[o*2+1]+=lazy[o]\n",
    "                lazy[o]=0\n",
    "            if L<=m:addone(o*2,l,m,L,R)\n",
    "            if m<R:addone(o*2+1,m+1,r,L,R)\n",
    "            sums[o]=sums[o*2]+sums[o*2+1]\n",
    "        ans=0\n",
    "        cursum=0\n",
    "        last={}\n",
    "        for i,x in enumerate(nums,1):\n",
    "            j=last.get(x,0)\n",
    "            cursum+=query(1,1,n,j+1,i)*2+i-j\n",
    "            addone(1,1,n,j+1,i)\n",
    "            # print(cursum)\n",
    "            ans=(ans+cursum)%(10**9+7)\n",
    "            last[x]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        tree = [None]*(4*n)\n",
    "        def build(t,l,r):\n",
    "            if(l == r):\n",
    "                tree[t] = [0,l,r,0]\n",
    "                return\n",
    "            m = (l+r)>>1\n",
    "            build(2*t,l,m)\n",
    "            build(2*t+1,m+1,r)\n",
    "            tree[t] = [0,l,r,0]\n",
    "            return \n",
    "        def pushdown(t):\n",
    "            lazy = tree[t][3]\n",
    "            tree[2*t][0] += lazy*(tree[2*t][2]-tree[2*t][1]+1) \n",
    "            tree[2*t][3] += lazy \n",
    "            tree[2*t+1][0] += lazy*(tree[2*t+1][2]-tree[2*t+1][1]+1) \n",
    "            tree[2*t+1][3] += lazy\n",
    "            tree[t][3] = 0\n",
    "            return\n",
    "        def update(t,ul,ur):\n",
    "            v, l, r, lazy = tree[t]\n",
    "            if(ul <= l and r <= ur):\n",
    "                tree[t][0] += (r-l+1)\n",
    "                tree[t][3] += 1\n",
    "                return\n",
    "            if(lazy != 0):\n",
    "                pushdown(t)\n",
    "            m = (l+r)>>1\n",
    "            if(ul <= m):\n",
    "                update(2*t,ul,ur)\n",
    "            if(ur > m):\n",
    "                update(2*t+1,ul,ur)\n",
    "            tree[t][0] = tree[2*t][0] + tree[2*t+1][0]\n",
    "            return\n",
    "        def query(t,ql,qr):\n",
    "            if(ql > qr):\n",
    "                return 0\n",
    "            v, l, r, lazy = tree[t]\n",
    "            if(ql <= l and r <= qr):\n",
    "                return tree[t][0]\n",
    "            if(lazy != 0):\n",
    "                pushdown(t)\n",
    "            rsum = 0\n",
    "            m = (l+r)>>1\n",
    "            if(ql <= m):\n",
    "                rsum += query(2*t,ql,qr)\n",
    "            if(qr > m):\n",
    "                rsum += query(2*t+1,ql,qr)\n",
    "            return rsum\n",
    "        build(1,0,n-1)\n",
    "        mapping = {}\n",
    "        result = 0\n",
    "        rx = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            if(num not in mapping):\n",
    "                rx += query(1,0,i-1)*2 + i + 1 \n",
    "                update(1,0,i)\n",
    "            else:\n",
    "                j = mapping[num]\n",
    "                rx += query(1,j+1,i-1)*2+(i-1-j)+1\n",
    "                update(1,j+1,i)\n",
    "            result += rx % (10**9+7)\n",
    "            mapping[num] = i \n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        tree = [None]*(4*n)\n",
    "        def build(t,l,r):\n",
    "            if(l == r):\n",
    "                tree[t] = [0,l,r,0]\n",
    "                return\n",
    "            m = (l+r)>>1\n",
    "            build(2*t,l,m)\n",
    "            build(2*t+1,m+1,r)\n",
    "            tree[t] = [0,l,r,0]\n",
    "            return \n",
    "        def pushdown(t):\n",
    "            lazy = tree[t][3]\n",
    "            tree[2*t][0] += lazy*(tree[2*t][2]-tree[2*t][1]+1) \n",
    "            tree[2*t][3] += lazy \n",
    "            tree[2*t+1][0] += lazy*(tree[2*t+1][2]-tree[2*t+1][1]+1) \n",
    "            tree[2*t+1][3] += lazy\n",
    "            tree[t][3] = 0\n",
    "            return\n",
    "        def update(t,ul,ur):\n",
    "            v, l, r, lazy = tree[t]\n",
    "            if(ul <= l and r <= ur):\n",
    "                tree[t][0] += (r-l+1)\n",
    "                tree[t][3] += 1\n",
    "                return\n",
    "            if(lazy != 0):\n",
    "                pushdown(t)\n",
    "            m = (l+r)>>1\n",
    "            if(ul <= m):\n",
    "                update(2*t,ul,ur)\n",
    "            if(ur > m):\n",
    "                update(2*t+1,ul,ur)\n",
    "            tree[t][0] = tree[2*t][0] + tree[2*t+1][0]\n",
    "            return\n",
    "        def query(t,ql,qr):\n",
    "            if(ql > qr):\n",
    "                return 0\n",
    "            v, l, r, lazy = tree[t]\n",
    "            if(ql <= l and r <= qr):\n",
    "                return tree[t][0]\n",
    "            if(lazy != 0):\n",
    "                pushdown(t)\n",
    "            rsum = 0\n",
    "            m = (l+r)>>1\n",
    "            if(ql <= m):\n",
    "                rsum += query(2*t,ql,qr)\n",
    "            if(qr > m):\n",
    "                rsum += query(2*t+1,ql,qr)\n",
    "            return rsum\n",
    "        build(1,0,n-1)\n",
    "        mapping = {}\n",
    "        result = 0\n",
    "        rx = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            if(num not in mapping):\n",
    "                rx += query(1,0,i-1)*2 + i + 1 \n",
    "                update(1,0,i)\n",
    "            else:\n",
    "                j = mapping[num]\n",
    "                rx += query(1,j+1,i-1)*2+(i-1-j)+1\n",
    "                update(1,j+1,i)\n",
    "            result += rx % (10**9+7)\n",
    "            mapping[num] = i \n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        \n",
    "        s = [0] * (4 * n)\n",
    "        lazy = [0] * (4*n)\n",
    "        \n",
    "        def update(o, l, r, v):\n",
    "            s[o] += (r-l+1) * v\n",
    "            lazy[o] += v\n",
    "        \n",
    "        def query_and_add1(o, l, r, L, R):\n",
    "            \n",
    "            if L <= l and R >= r:\n",
    "                res = s[o]\n",
    "                update(o, l, r, 1)\n",
    "                return res\n",
    "\n",
    "            m = (l+r) // 2\n",
    "            a = lazy[o]\n",
    "            if a:\n",
    "                update(2*o, l, m, a)\n",
    "                update(2*o+1, m+1, r, a)\n",
    "                lazy[o] = 0\n",
    "            \n",
    "            res = 0\n",
    "            if L <= m: res += query_and_add1(2*o, l, m, L, R)\n",
    "            if m < R: res += query_and_add1(2*o+1, m+1, r, L, R)\n",
    "            s[o] = s[2*o] + s[2*o+1]\n",
    "            return res\n",
    "\n",
    "        mod = 10**9+7\n",
    "        w = {}\n",
    "        p = [0] * (n+1)\n",
    "        for i, v in enumerate(nums, 1):\n",
    "            j = w.get(v, 0)\n",
    "            t = query_and_add1(1, 1, n, j+1, i) * 2 + i - j\n",
    "            #print(t)\n",
    "            p[i] = p[i-1] + t\n",
    "            p[i] %= mod\n",
    "            w[v] = i\n",
    "            #print(p)\n",
    "        return sum(p) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTree():\n",
    "    def __init__(self, nums: list[int]) -> None:\n",
    "        n = len(nums)\n",
    "        self.nums = nums\n",
    "        self.d = [[0, 0] for _ in range(4 * n)]\n",
    "        self.b = [0] * (4 * n)\n",
    "        self.build(0, 0, n - 1)\n",
    "\n",
    "    def pushup(self, i: int) -> None:\n",
    "        d = self.d\n",
    "        d[i][0] = d[2 * i + 1][0] + d[2 * i + 2][0]\n",
    "        d[i][1] = d[2 * i + 1][1] + d[2 * i + 2][1]\n",
    "\n",
    "    def pushdown(self, i: int, l: int, r: int) -> None:\n",
    "        d, b = self.d, self.b\n",
    "        m = (l + r) // 2\n",
    "        b[2 * i + 1] += b[i]\n",
    "        b[2 * i + 2] += b[i]\n",
    "        d[2 * i + 1][1] += 2 * b[i] * d[2 * i + 1][0] + (m - l + 1) * b[i] ** 2\n",
    "        d[2 * i + 2][1] += 2 * b[i] * d[2 * i + 2][0] + (r - m) * b[i] ** 2\n",
    "        d[2 * i + 1][0] += (m - l + 1) * b[i]\n",
    "        d[2 * i + 2][0] += (r - m) * b[i]\n",
    "        b[i] = 0\n",
    "\n",
    "    def build(self, i: int, l: int, r: int) -> None:\n",
    "        nums, d = self.nums, self.d\n",
    "        if l == r:\n",
    "            d[l][0] = d[l][1] = nums[l]\n",
    "            return\n",
    "        m = (l + r) // 2\n",
    "        self.build(2 * i + 1, l, m)\n",
    "        self.build(2 * i + 2, m + 1, r)\n",
    "        self.pushup(i)\n",
    "    \n",
    "    def update(self, i: int, l: int, r: int, x: int, L: int, R: int) -> None:\n",
    "        d, b = self.d, self.b\n",
    "        if L <= l and r <= R:\n",
    "            d[i][1] += 2 * d[i][0] + (r - l + 1)\n",
    "            d[i][0] += (r - l + 1) * x\n",
    "            b[i] += x\n",
    "            return\n",
    "        if b[i]:\n",
    "            self.pushdown(i, l, r)\n",
    "        m = (l + r) // 2\n",
    "        if m >= L:\n",
    "            self.update(2 * i + 1, l, m, x, L, R)\n",
    "        if m < R:\n",
    "            self.update(2 * i + 2, m + 1, r, x, L, R)\n",
    "        self.pushup(i)\n",
    "\n",
    "    def query(self, i: int, l: int, r: int, L: int, R: int) -> List[int]:\n",
    "        d, b = self.d, self.b\n",
    "        if L <= l and r <= R:\n",
    "            return d[i]\n",
    "        if b[i]:\n",
    "            self.pushdown(i, l, r)\n",
    "        res = [0, 0]\n",
    "        m = (l + r) // 2\n",
    "        if m >= L:\n",
    "            res1, res2 = self.query(2 * i + 1, l, m, L, R)\n",
    "            res[0] += res1\n",
    "            res[1] += res2\n",
    "        if m < R:\n",
    "            res1, res2 = self.query(2 * i + 2, m + 1, r, L, R)\n",
    "            res[0] += res1\n",
    "            res[1] += res2\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        last = {}\n",
    "        n = len(nums)\n",
    "        arr = [0] * n\n",
    "        st = SegmentTree(arr)\n",
    "        ans = 0\n",
    "        s = ss = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x not in last:\n",
    "                st.update(0, 0, n - 1, 1, 0, i)\n",
    "            else:\n",
    "                st.update(0, 0, n - 1, 1, last[x] + 1, i)\n",
    "            last[x] = i\n",
    "            # print(st.d)\n",
    "            ans += st.query(0, 0, n - 1, 0, n - 1)[1]\n",
    "            ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.begin = 0\n",
    "        self.end = 0\n",
    "        self.sum = 0 #本段的所有数字的和,不算被上层盘剥的\n",
    "        self.cache = 0 # 对下层的盘剥次数\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self,begin,end):\n",
    "        self.root = Node()\n",
    "        self.root.begin = begin\n",
    "        self.root.end = end\n",
    "    \n",
    "    def querySum(self,begin,end):\n",
    "        return self.internal_querySum(self.root,begin,end,0)\n",
    "\n",
    "    def update(self,begin,end):\n",
    "        return self.internal_update(self.root,begin,end)\n",
    "\n",
    "    def internal_querySum(self,node,begin,end,c):\n",
    "        if end<node.begin or begin>node.end:\n",
    "            return 0\n",
    "        if begin<=node.begin and end>=node.end:\n",
    "            return node.sum + (node.end-node.begin+1)*c\n",
    "\n",
    "        if node.left==None: #没有子层\n",
    "            mid = (node.begin+node.end)//2\n",
    "            \n",
    "            node.left = Node()\n",
    "            node.left.begin = node.begin\n",
    "            node.left.end = mid\n",
    "            node.left.sum = node.sum*(node.left.end-node.left.begin+1)//(node.end-node.begin+1)\n",
    "\n",
    "            node.right = Node()\n",
    "            node.right.begin = mid + 1\n",
    "            node.right.end = node.end\n",
    "            node.right.sum = node.sum*(node.right.end-node.right.begin+1)//(node.end-node.begin+1)\n",
    "\n",
    "        ret =  self.internal_querySum(node.left,begin,end,c+node.cache)\n",
    "        ret += self.internal_querySum(node.right,begin,end,c+node.cache)\n",
    "        return ret\n",
    "\n",
    "\n",
    "    def internal_update(self,node,begin,end):\n",
    "        if end<node.begin or begin>node.end:\n",
    "            return 0\n",
    "        if begin<=node.begin and end>=node.end:\n",
    "            node.sum += node.end-node.begin+1\n",
    "            node.cache += 1\n",
    "            return node.end-node.begin+1\n",
    "\n",
    "        if node.left==None: #没有子层\n",
    "            mid = (node.begin+node.end)//2\n",
    "\n",
    "            node.left = Node()\n",
    "            node.left.begin = node.begin\n",
    "            node.left.end = mid\n",
    "            node.left.sum = node.sum*(node.left.end-node.left.begin+1)//(node.end-node.begin+1)\n",
    "\n",
    "            node.right = Node()\n",
    "            node.right.begin = mid + 1\n",
    "            node.right.end = node.end\n",
    "            node.right.sum = node.sum*(node.right.end-node.right.begin+1)//(node.end-node.begin+1)\n",
    "\n",
    "        #打破本层 则本层的累积要下放\n",
    "\n",
    "\n",
    "        ret =  self.internal_update(node.left,begin,end)\n",
    "        ret += self.internal_update(node.right,begin,end)\n",
    "\n",
    "        node.sum += ret\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        d = {}\n",
    "        #需要[0,len(nums)-1]的线段树\n",
    "        ST = SegTree(0,len(nums)-1)\n",
    "        sqs = 0 #平方和\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            num = nums[i]\n",
    "\n",
    "            ni = d.get(num,len(nums))\n",
    "            d[num] = i\n",
    "\n",
    "            nsqs = sqs + ni - i\n",
    "            v = 0\n",
    "            if i+1<=ni-1:\n",
    "                v = ST.querySum(i+1,ni-1) #在线段树中查询[i+1,ni-1]的和\n",
    "            #print(i+1,ni-1,v)\n",
    "            nsqs += 2*v\n",
    "            #print(\"nsqs\",nsqs)\n",
    "            ST.update(i,ni-1)#在线段树中给区间[i,ni-1]加一\n",
    "\n",
    "            ret += nsqs\n",
    "            ret %= 1000000007\n",
    "            #print(\"ret\",ret)\n",
    "            sqs = nsqs\n",
    "        return ret\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, val=0, start=-10**9, end=10**9 ) -> None:\n",
    "        node_num = end - start + 1\n",
    "        self.tree = [val] * 4 * node_num\n",
    "        self.lazy = [0] * 4 * node_num\n",
    "        self.start = start\n",
    "        self.end = end \n",
    "      \n",
    "\n",
    "    def update(self, l, r, val):\n",
    "        def _update(start=self.start, end=self.end, node=0):\n",
    "            if l <= start and end <= r:\n",
    "                self.tree[node] += (end - start + 1) * val\n",
    "                self.lazy[node] += val\n",
    "                return \n",
    "            \n",
    "            mid = math.floor((start + end) / 2)\n",
    "            self.pushDown(node, mid - start + 1, end - mid)\n",
    "            if l <= mid:\n",
    "                _update(start, mid, 2*node+1)\n",
    "            if r > mid:\n",
    "                _update(mid + 1, end, 2*node+2)\n",
    "            self.pushUp(node)\n",
    "        _update()\n",
    "        \n",
    "\n",
    "    def query(self, l, r):\n",
    "        def _query(node=0, start=self.start, end=self.end): #max\n",
    "            if l <= start and end <= r:\n",
    "                t = self.tree[node]\n",
    "                self.tree[node] += (end - start + 1)\n",
    "                self.lazy[node] += 1\n",
    "                return t\n",
    "            mid = math.floor((start + end) / 2) \n",
    "            ans = 0\n",
    "            self.pushDown(node, mid - start + 1, end - mid)\n",
    "            if l <= mid: \n",
    "                ans += _query(2*node+1, start, mid)\n",
    "            if r > mid: \n",
    "                ans += _query(2*node+2, mid + 1, end)\n",
    "            self.pushUp(node)\n",
    "            return ans \n",
    "\n",
    "        return _query()\n",
    "    \n",
    "\n",
    "    def pushDown(self, node, leftNum, rightNum):\n",
    "        if self.lazy[node] == 0:\n",
    "            return\n",
    "        self.tree[2*node+1] += self.lazy[node] * leftNum\n",
    "        self.tree[2*node+2] += self.lazy[node] * rightNum\n",
    "        # 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖\n",
    "        self.lazy[2*node+1] += self.lazy[node]\n",
    "        self.lazy[2*node+2] += self.lazy[node]\n",
    "        self.lazy[node] = 0\n",
    "\n",
    "    def pushUp(self, node):\n",
    "        self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]\n",
    "\n",
    "            \n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        seg = SegTree(0, -1, nums.__len__()-1)\n",
    "        last = defaultdict(lambda: -1)\n",
    "        sum = 0 \n",
    "        cur_sum = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            last_i = last[v]\n",
    "            cur_sum += 2*seg.query(last_i+1, i) + i - last_i\n",
    "            sum += cur_sum % (10**9+7)\n",
    "            # seg.update(last_i+1, i, 1)\n",
    "            last[v] = i\n",
    "            \n",
    "        return sum % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "\n",
    "        def build(node, start, end):\n",
    "            if start == end:\n",
    "                tree[node] = arr[start]\n",
    "            else:\n",
    "                mid = (start + end) // 2\n",
    "                build(2 * node, start, mid)\n",
    "                build(2 * node + 1, mid + 1, end)\n",
    "                tree[node] = tree[2 * node] + tree[2 * node + 1]\n",
    "\n",
    "        def update(node, start, end, left, right, value):\n",
    "            if lazy[node] != 0:\n",
    "                tree[node] += (end - start + 1) * lazy[node]\n",
    "                if start != end:\n",
    "                    lazy[2 * node] += lazy[node]\n",
    "                    lazy[2 * node + 1] += lazy[node]\n",
    "                lazy[node] = 0\n",
    "\n",
    "            if start > right or end < left:\n",
    "                return\n",
    "\n",
    "            if start >= left and end <= right:\n",
    "                tree[node] += (end - start + 1) * value\n",
    "                if start != end:\n",
    "                    lazy[2 * node] += value\n",
    "                    lazy[2 * node + 1] += value\n",
    "                return\n",
    "\n",
    "            mid = (start + end) // 2\n",
    "            update(2 * node, start, mid, left, right, value)\n",
    "            update(2 * node + 1, mid + 1, end, left, right, value)\n",
    "            tree[node] = tree[2 * node] + tree[2 * node + 1]\n",
    "\n",
    "        def query(node, start, end, left, right):\n",
    "            if lazy[node] != 0:\n",
    "                tree[node] += (end - start + 1) * lazy[node]\n",
    "                if start != end:\n",
    "                    lazy[2 * node] += lazy[node]\n",
    "                    lazy[2 * node + 1] += lazy[node]\n",
    "                lazy[node] = 0\n",
    "\n",
    "            if start > right or end < left:\n",
    "                return 0\n",
    "\n",
    "            if start >= left and end <= right:\n",
    "                return tree[node]\n",
    "\n",
    "            mid = (start + end) // 2\n",
    "            left_sum = query(2 * node, start, mid, left, right)\n",
    "            right_sum = query(2 * node + 1, mid + 1, end, left, right)\n",
    "            return left_sum + right_sum\n",
    "\n",
    "        n = len(nums)\n",
    "        arr = [0] * n\n",
    "        tree = [0] * (4 * len(arr))\n",
    "        lazy = [0] * (4 * len(arr))\n",
    "        build(1, 0, len(arr) - 1)\n",
    "\n",
    "        dic = {}\n",
    "        ans, cur = 0, 0\n",
    "        for i, num in enumerate(nums):\n",
    "            l = dic.get(num, -1)\n",
    "            t = query(1, 0, n, l + 1, i)\n",
    "            cur = (cur + t * 2 + i - l) % kmod\n",
    "            ans = (ans + cur) % kmod\n",
    "            dic[num] = i\n",
    "            update(1, 0, n, l + 1, i, 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        A=10**9+7\n",
    "        dic=dict()\n",
    "        lazylen=[0]*4*len(nums)\n",
    "        lentree=[0]*4*len(nums)\n",
    "        def update(n,l,r,tl,tr,val):\n",
    "            if l==tl and r==tr:\n",
    "                lazylen[n]+=1\n",
    "                lentree[n]+=(r-l)\n",
    "                return \n",
    "            m=(l+r)//2\n",
    "            if tr<=m:\n",
    "                update(2*n+1,l,m,tl,tr,val)\n",
    "            elif tl>=m:\n",
    "                update(2*n+2,m,r,tl,tr,val)\n",
    "            else:\n",
    "                update(2*n+1,l,m,tl,m,val)\n",
    "                update(2*n+2,m,r,m,tr,val)\n",
    "            lentree[n]=lentree[2*n+1]+lentree[2*n+2]+lazylen[n]*(r-l)\n",
    "        def find(n,l,r,tl,tr):\n",
    "            m=(r+l)//2\n",
    "            if lazylen[n]!=0:\n",
    "                if r-l!=1:\n",
    "                    lazylen[2*n+1]+=lazylen[n]\n",
    "                    lentree[2*n+1]+=(lazylen[n]*(m-l))\n",
    "                    lazylen[2*n+2]+=lazylen[n]\n",
    "                    lentree[2*n+2]+=(lazylen[n]*(r-m))\n",
    "                lazylen[n]=0\n",
    "            if l==tl and r==tr:\n",
    "                return lentree[n]\n",
    "            if tr<=m:\n",
    "                return find(2*n+1,l,m,tl,tr)\n",
    "            elif tl>=m:\n",
    "                return find(2*n+2,m,r,tl,tr)\n",
    "            else:\n",
    "                return find(2*n+1,l,m,tl,m)+find(2*n+2,m,r,m,tr)\n",
    "        ans=0\n",
    "        last=0\n",
    "        for i in range(len(nums)):\n",
    "            left=dic.get(nums[i],-1)+1\n",
    "            last=(last+i+1-left+2*(find(0,0,len(nums),left,i+1)))%A\n",
    "            update(0,0,len(nums),left,i+1,nums[i])\n",
    "            ans=(ans+last)%A\n",
    "            dic[nums[i]]=i\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        sum=[0]*(4*n)\n",
    "        todo=[0]*(4*n)\n",
    "\n",
    "        def do(o,l,r,add):\n",
    "            sum[o]+=add*(r-l+1)\n",
    "            todo[o]+=add\n",
    "        def query_and_add1(o,l,r,L,R):\n",
    "            if L<=l and r<=R:\n",
    "                res=sum[o]\n",
    "                do(o,l,r,1)\n",
    "                return res\n",
    "            m=(l+r)//2\n",
    "            add=todo[o]\n",
    "            if add:\n",
    "                do(o*2,l,m,add)\n",
    "                do(o*2+1,m+1,r,add)\n",
    "                todo[o]=0\n",
    "            res=0\n",
    "            if L<=m:res+=query_and_add1(o*2,l,m,L,R)\n",
    "            if m<R: res+=query_and_add1(o*2+1,m+1,r,L,R)\n",
    "            sum[o]=sum[o*2]+sum[o*2+1]\n",
    "            return res\n",
    "        ans=s=0\n",
    "        last={}\n",
    "        for i, x in enumerate(nums,1):\n",
    "            j=last.get(x,0)\n",
    "            s+=query_and_add1(1,1,n,j+1,i)*2+i-j\n",
    "            ans+=s\n",
    "            last[x]=i\n",
    "        return ans%1_000_000_007\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums):\n",
    "        n = len(nums)\n",
    "        M = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        p = [-1] * 100001\n",
    "        \n",
    "        sq = [0] * (4 * n + 1)\n",
    "        sm = [0] * (4 * n + 1)\n",
    "        t = [0] * (4 * n + 1)\n",
    "        \n",
    "        def update(k, p, q, u, v, g):\n",
    "            if p == u and q == v:\n",
    "                d = q - p + 1\n",
    "                e = 2 * (sm[k] + d * g) + d\n",
    "                sq[k] = (sq[k] + e) % M\n",
    "                sm[k] = (sm[k] + d) % M\n",
    "                t[k] += 1\n",
    "                return e\n",
    "            g += t[k]\n",
    "            m = (p + q) >> 1\n",
    "            s = 0\n",
    "            if u <= m:\n",
    "                s += update(k << 1, p, m, u, min(m, v), g)\n",
    "            if v > m:\n",
    "                s += update((k << 1) + 1, m + 1, q, max(u, m + 1), v, g)\n",
    "            sq[k] = (sq[k] + s) % M\n",
    "            sm[k] = (sm[k] + v - u + 1) % M\n",
    "            return s\n",
    "        \n",
    "        \n",
    "        for i in range(n):\n",
    "            update(1, 0, n - 1, p[nums[i]] + 1 ,i, 0)\n",
    "            ans = (ans + sq[1]) % M\n",
    "            p[nums[i]] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        t2 = collections.defaultdict(int)\n",
    "        t1 = [0]\n",
    "        mod = int(1e9 + 7)\n",
    "        for i in range(len(nums)):\n",
    "            t1.append(t2[nums[i]])\n",
    "            t2[nums[i]] = i + 1\n",
    "        t = [[0, 0] for _ in range(4 * len(nums))]\n",
    "        tag = [0] * (4 * len(nums))\n",
    "        def pushdown(x, l, r):\n",
    "            if tag[x] > 0:\n",
    "                tag[x * 2] += tag[x]\n",
    "                t[x * 2][0] = t[x * 2][0] + 2 * tag[x] * t[x * 2][1] + tag[x] ** 2 * ((l + r) // 2 - l + 1)\n",
    "                t[x * 2][1] = t[x * 2][1] + tag[x] * ((l + r) // 2 - l + 1)\n",
    "                tag[x * 2 + 1] += tag[x]\n",
    "                t[x * 2 + 1][0] = t[x * 2 + 1][0] + 2 * tag[x] * t[x * 2 + 1][1] + tag[x] ** 2 * (r - (l + r) // 2)\n",
    "                t[x * 2 + 1][1] = t[x * 2 + 1][1] + tag[x] * (r - (l + r) // 2)\n",
    "                tag[x] = 0\n",
    "        def pushup(x):\n",
    "            t[x][0] = t[x * 2][0] + t[x * 2 + 1][0]\n",
    "            t[x][1] = t[x * 2][1] + t[x * 2 + 1][1]\n",
    "        def query(x, L, R, l, r):\n",
    "            if l >= L and r <= R:\n",
    "                return t[x]\n",
    "            mid = (l + r) // 2\n",
    "            ans = [0, 0]\n",
    "            pushdown(x, l, r)\n",
    "            if L <= mid:\n",
    "                t3 = query(x * 2, L, R, l, mid)\n",
    "                ans[0] += t3[0]\n",
    "                ans[1] += t3[1]\n",
    "            if mid < R:\n",
    "                t3 = query(x * 2 + 1, L, R, mid + 1, r)\n",
    "                ans[0] += t3[0]\n",
    "                ans[1] += t3[1]\n",
    "            return ans\n",
    "        def update(x, L, R, l, r):\n",
    "            if l >= L and r <= R:\n",
    "                tag[x] += 1\n",
    "                t[x][0] = t[x][0] + 2 * t[x][1] + (r - l + 1)\n",
    "                t[x][1] = t[x][1] + (r - l + 1)\n",
    "                return\n",
    "            mid = (l + r) // 2\n",
    "            pushdown(x, l, r)\n",
    "            if L <= mid:\n",
    "                update(x * 2, L, R, l, mid)\n",
    "            if mid < R:\n",
    "                update(x * 2 + 1, L, R, mid + 1, r)\n",
    "            pushup(x)\n",
    "        # s1, s2 = [0] * (len(nums) + 1), [0] * (len(nums) + 1)\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            # x, y, z = s2[t1[i]], s1[i - 1] - s1[t1[i]], s2[i - 1] - s2[t1[i]]\n",
    "            update(1, t1[i] + 1, i, 1, len(nums))\n",
    "            x = query(1, 1, i, 1, len(nums))\n",
    "            ans += x[0]\n",
    "            ans %= mod\n",
    "            # print(ans, s1, s2)\n",
    "        # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: list[int]) -> int:\n",
    "        n = len(nums)\n",
    "        tr = [0] * (4 * n + 2)\n",
    "        lazy = [0] * (4 * n + 2)\n",
    "\n",
    "        def update(l: int, r: int, val: int, now=1, L=1, R=n):\n",
    "            if l <= L and R <= r:\n",
    "                tr[now] += (R - L + 1) * val\n",
    "                lazy[now] += val\n",
    "            else:\n",
    "                mid = (L + R) >> 1\n",
    "                if l <= mid and L <= r:\n",
    "                    update(l, r, val, now << 1, L, mid)\n",
    "                if l <= R and mid + 1 <= r:\n",
    "                    update(l, r, val, now << 1 | 1, mid + 1, R)\n",
    "                up(now)\n",
    "\n",
    "        def down(now, L, R):\n",
    "            x = lazy[now]\n",
    "            if x != 0:\n",
    "                mid = (L + R) >> 1\n",
    "                tr[now << 1] += (mid - L + 1) * x\n",
    "                tr[now << 1 | 1] += (R - mid) * x\n",
    "                lazy[now << 1] += x\n",
    "                lazy[now << 1 | 1] += x\n",
    "                lazy[now] = 0\n",
    "\n",
    "        def up(now):\n",
    "            tr[now] = tr[now << 1] + tr[now << 1 | 1]\n",
    "\n",
    "        def query(l: int, r: int, now=1, L=1, R=n):\n",
    "            if l <= L and R <= r:\n",
    "                return tr[now]\n",
    "            mid = (L + R) >> 1\n",
    "            down(now, L, R)\n",
    "            res = 0\n",
    "            if l <= mid and L <= r:\n",
    "                res += query(l, r, now << 1, L, mid)\n",
    "            if l <= R and mid + 1 <= r:\n",
    "                res += query(l, r, now << 1 | 1, mid + 1, R)\n",
    "            return res\n",
    "\n",
    "        s_2 = [0] * (n + 1)\n",
    "        d = dict()\n",
    "        for i, x in enumerate(nums, 1):\n",
    "            last = d.get(x, 0)\n",
    "            gain = i - last + query(last + 1, i) * 2\n",
    "            update(last + 1, i, 1)\n",
    "            s_2[i] = s_2[i - 1] + gain\n",
    "            d[x] = i\n",
    "        return sum(s_2) % int(1e9 + 7)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution {\n",
    "# public:\n",
    "#     int sumCounts(vector<int>& nums) {\n",
    "#         int n = nums.size();\n",
    "\n",
    "#         const int MOD = 1e9 + 7;\n",
    "# \t\t// sum1：区间和，sum2：区间平方和\n",
    "#         long long sum1[n * 4 + 10], sum2[n * 4 + 10];\n",
    "# \t\t// 因为是区间修改，所以要懒标记下推\n",
    "#         int lazy[n * 4 + 10];\n",
    "#         memset(sum1, 0, sizeof(sum1)); memset(sum2, 0, sizeof(sum2));\n",
    "#         memset(lazy, 0, sizeof(lazy));\n",
    "\n",
    "# \t\t// 根据公式维护区间加 K\n",
    "#         auto add = [&](int id, int l, int r, int K) {\n",
    "#             int len = r - l + 1;\n",
    "#             sum2[id] = (sum2[id] + 2LL * K * sum1[id] + 1LL * K * K % MOD * len) % MOD;\n",
    "#             sum1[id] = (sum1[id] + 1LL * K * len) % MOD;\n",
    "#         };\n",
    "\n",
    "# \t\t// 懒标记下推\n",
    "#         auto down = [&](int id, int l, int r) {\n",
    "#             int nxt = id << 1, mid = (l + r) >> 1;\n",
    "#             lazy[nxt] += lazy[id]; add(nxt, l, mid, lazy[id]);\n",
    "#             lazy[nxt | 1] += lazy[id]; add(nxt | 1, mid + 1, r, lazy[id]);\n",
    "#             lazy[id] = 0;\n",
    "#         };\n",
    "\n",
    "# \t\t// 区间加 1\n",
    "#         function<void(int, int, int, int, int)> modify = [&](int id, int l, int r, int ql, int qr) {\n",
    "#             if (ql <= l && r <= qr) {\n",
    "#                 add(id, l, r, 1);\n",
    "#                 lazy[id]++;\n",
    "#             } else {\n",
    "#                 if (lazy[id]) down(id, l, r);\n",
    "#                 int nxt = id << 1, mid = (l + r) >> 1;\n",
    "#                 if (ql <= mid) modify(nxt, l, mid, ql, qr);\n",
    "#                 if (qr > mid) modify(nxt | 1, mid + 1, r, ql, qr);\n",
    "#                 sum1[id] = (sum1[nxt] + sum1[nxt | 1]) % MOD;\n",
    "#                 sum2[id] = (sum2[nxt] + sum2[nxt | 1]) % MOD;\n",
    "#             }\n",
    "#         };\n",
    "\n",
    "#         long long ans = 0;\n",
    "# \t\t// last[x] 表示元素 x 最近出现在哪个下标\n",
    "#         unordered_map<int, int> last;\n",
    "#         for (int i = 1; i <= n; i++) {\n",
    "#             int &old = last[nums[i - 1]];\n",
    "#             modify(1, 1, n, old + 1, i);\n",
    "#             old = i;\n",
    "# \t\t\t// 答案就是 [1, i] 这段区间的 sum2 之和\n",
    "#             ans = (ans + sum2[1]) % MOD;\n",
    "#         }\n",
    "#         return ans;\n",
    "#     }\n",
    "# };\n",
    "\n",
    "# 作者：TsReaper\n",
    "# 链接：https://leetcode.cn/circle/discuss/SwnhNk/view/qPvGAf/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        \n",
    "        sum1 = [0] * (n * 4 + 10)\n",
    "        sum2 = [0] * (n * 4 + 10)\n",
    "        lazy = [0] * (n * 4 + 10)\n",
    "        \n",
    "        def add(i, l, r, k):\n",
    "            le = r - l + 1\n",
    "            sum2[i] = (sum2[i] + 2 * k * sum1[i] + k * k % MOD * le) % MOD\n",
    "            sum1[i] = (sum1[i] + k * le) % MOD\n",
    "        \n",
    "        def down(i, l, r):\n",
    "            nxt = i << 1\n",
    "            mid = l + r >> 1\n",
    "            lazy[nxt] += lazy[i]\n",
    "            add(nxt, l, mid, lazy[i])\n",
    "            lazy[nxt | 1] += lazy[i]\n",
    "            add(nxt | 1, mid + 1, r, lazy[i])\n",
    "            lazy[i] = 0\n",
    "        \n",
    "        def modify(i, l, r, ql, qr):\n",
    "            if ql <= l and r <= qr:\n",
    "                add(i, l, r, 1)\n",
    "                lazy[i] += 1\n",
    "            else:\n",
    "                if lazy[i] > 0:\n",
    "                    down(i, l, r)\n",
    "                nxt = i << 1\n",
    "                mid = l + r >> 1\n",
    "                if ql <= mid:\n",
    "                    modify(nxt, l, mid, ql, qr)\n",
    "                if qr > mid:\n",
    "                    modify(nxt | 1, mid + 1, r, ql, qr)\n",
    "                sum1[i] = (sum1[nxt] + sum1[nxt | 1]) % MOD\n",
    "                sum2[i] = (sum2[nxt] + sum2[nxt | 1]) % MOD\n",
    "        \n",
    "        ans = 0\n",
    "        last = defaultdict(int)\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            prev = last[nums[i - 1]]\n",
    "            modify(1, 1, n, prev + 1, i)\n",
    "            last[nums[i - 1]] = i\n",
    "            ans = (ans + sum2[1]) % MOD\n",
    "        \n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        M = 10**9 + 7\n",
    "        sm = [0] * (n * 4)\n",
    "        todo = [0] * (n * 4)\n",
    "        def maintain(o):\n",
    "            sm[o] = sm[o * 2] + sm[o * 2 + 1]\n",
    "        \n",
    "        def do(o, l, r, add):\n",
    "            sm[o] += (r - l + 1) * add\n",
    "            todo[o] += add\n",
    "        \n",
    "        def build(o, l, r):\n",
    "            if l == r:\n",
    "                sm[o] = nums[l - 1]\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2 , l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o)\n",
    "            \n",
    "        def query_and_add1(o, l, r, L, R):\n",
    "            if L <= l and r <= R:\n",
    "                res = sm[o]\n",
    "                do(o, l, r, 1)\n",
    "                return res\n",
    "            res = 0\n",
    "            m = (l + r) // 2\n",
    "            if todo[o]:\n",
    "                do(o * 2, l, m, todo[o])\n",
    "                do(o * 2 + 1, m + 1, r, todo[o])\n",
    "                todo[o] = 0\n",
    "            if m >= L: res += query_and_add1(o * 2, l, m, L, R)\n",
    "            if m < R: res += query_and_add1(o * 2 + 1, m + 1, r, L, R)\n",
    "            maintain(o)\n",
    "            return res\n",
    "            \n",
    "        last = {}\n",
    "        cur = ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            j = last.get(num, -1)\n",
    "            cur += i - j + (query_and_add1(1, 1, n, j + 2, i + 1)) * 2\n",
    "            ans = (ans + cur) % M\n",
    "            last[num] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''2916 子数组不同元素数目平方和\n",
    "    给你一个下标从 0 开始的整数数组 nums 。定义 nums 一个子数组的 不同计数 值如下：\n",
    "    令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组\n",
    "    （满足 0 <= i <= j < nums.length ），那么我们称子数组 nums[i..j] 中不同值的数目\n",
    "    为 nums[i..j] 的不同计数。\n",
    "    请你返回 nums 中所有子数组的 不同计数 的 平方 和。由于答案可能会很大，请你将它对 \n",
    "    10**9 + 7 取余 后返回。子数组指的是一个数组里面一段连续 非空 的元素序列。\n",
    "    '''\n",
    "    def sumCounts(self, nums: list[int]) -> int:\n",
    "        '''segment tree of square_sum.'''\n",
    "        if nums: # 建立线段树对象\n",
    "            self.ins = self.SegTree(nums) # 初始化线段树对象，求和。\n",
    "            \n",
    "        else: \n",
    "            raise ValueError\n",
    "        \n",
    "        cutnum = 10 ** 9 + 7 # 极大值，取模数\n",
    "        re = 0; sum2 = 0; n = 1; lent = nums.__len__()\n",
    "        last_index_dic = dict() # 存放最后的列值的索引\n",
    "        while n < lent + 1:\n",
    "            # mi用来存放与索引 n - 1值相同的前一个索引+1\n",
    "            mi = last_index_dic.get(self.ins.lis[n-1], -1) + 1\n",
    "            # mi ~ n 之间增加1后的平方和累加\n",
    "            sum2 += 2 * self.ins.get_section_val(0, lent, mi, n) + (n - mi)\n",
    "            # 完成累加\n",
    "            self.ins.set_section_increas(0, lent, mi, n)\n",
    "            # 积累平方和的值\n",
    "            re += sum2 % cutnum\n",
    "            # 更新值，索引字典\n",
    "            last_index_dic[self.ins.lis[n-1]] = n - 1\n",
    "            n += 1\n",
    "\n",
    "        return re % cutnum\n",
    "        \n",
    "    class SegTree:\n",
    "        '''segment tree Node'''\n",
    "        class NodeTree:\n",
    "            '''带有lazy标记的节点'''\n",
    "            def __init__(self, val, lazy=0) -> None:\n",
    "                self.val = val; self.lazy = lazy\n",
    "        \n",
    "        def __init__(self, lis: list) -> None:\n",
    "            if lis.__len__():\n",
    "                self.lis = lis\n",
    "                self.treelis = [self.NodeTree(0) for i in range(len(lis) * 4)]\n",
    "            else:\n",
    "                print('blank list.')\n",
    "                raise ValueError\n",
    "\n",
    "        def build_tree(self, start: int, end: int, node: int=1) -> None:\n",
    "            '''建立线段数'''\n",
    "            if end - start < 2:\n",
    "                self.treelis[node].val = self.lis[start]\n",
    "            else:\n",
    "                lnode = node * 2; rnode = node * 2 + 1\n",
    "                mid = (start + end) >> 1\n",
    "                self.build_tree(start, mid, lnode)\n",
    "                self.build_tree(mid, end, rnode)\n",
    "                self.treelis[node].val = self.treelis[lnode].val\\\n",
    "                    + self.treelis[rnode].val\n",
    "                \n",
    "        def push_lazy_down(self, start: int, end: int, node: int) -> None:\n",
    "            '''将lazy标志下发到下一层节点'''\n",
    "            \n",
    "            if end - start > 1: # 判断是否叶子节点\n",
    "                p = self.treelis[node].lazy\n",
    "                if p: # 判断是否本节点有lazy标记\n",
    "                    # 找到下一层节点\n",
    "                    lnode = 2 * node; rnode = 2 * node + 1\n",
    "                    mid = (start + end) >> 1\n",
    "                    # 改变下层节点的值\n",
    "                    self.treelis[lnode].val += p * (mid - start)\n",
    "                    self.treelis[rnode].val += p * (end -   mid)\n",
    "                    # 修改下层节点标记\n",
    "                    self.treelis[lnode].lazy += p\n",
    "                    self.treelis[rnode].lazy += p\n",
    "                    # 修改本层节点标记\n",
    "                    self.treelis[node].lazy = 0\n",
    "\n",
    "        def get_single_index(self, start:int, end: int, i: int, node = 1):\n",
    "            '''获取lis中特定下标的值'''\n",
    "            if i < start or i >= end: # 越界索引判断并剔除\n",
    "                raise IndexError\n",
    "            elif (start == i) and (end - start < 2): # 递归出口，叶子节点判断\n",
    "                return self.treelis[node].val\n",
    "            else:\n",
    "                self.push_lazy_down(start, end, node) # lazy标记下发\n",
    "                lnode = node * 2; rnode = node * 2 + 1\n",
    "                mid = (start + end) >> 1\n",
    "                if start <= i < mid:\n",
    "                    return self.get_single_index(start, mid, i, lnode)\n",
    "                else:\n",
    "                    return self.get_single_index(mid, end, i, rnode)\n",
    "\n",
    "        def update_single_index(self, start:int, end: int, i: int, val: int,\\\n",
    "                                node = 1):\n",
    "            '''获取指定下标的，节点的值'''\n",
    "            if i < start or i >= end: # 越界索引判断并剔除\n",
    "                raise IndexError\n",
    "            elif start == i and end - start < 2: # 递归出口，叶子节点判断\n",
    "                self.treelis[node].val = val\n",
    "            else:\n",
    "                self.push_lazy_down(start, end, node) # lazy标记下发\n",
    "                lnode = node * 2; rnode = node * 2 + 1\n",
    "                mid = (start + end) >> 1\n",
    "                if start <= i < mid:\n",
    "                    self.update_single_index(start, mid, i, val, lnode)\n",
    "                else:\n",
    "                    self.update_single_index(mid, end, i, val, rnode)\n",
    "                self.treelis[node].val = self.treelis[lnode].val\\\n",
    "                    + self.treelis[rnode].val\n",
    "                \n",
    "        def get_section_val(self, start: int, end: int, lb: int, rb: int, \n",
    "                            node: int=1):\n",
    "            '''获取区间内的值（包含）,start：线段树左边界；L区间的左边界'''\n",
    "            if lb > rb: # 给定区间越界判断\n",
    "                raise IndexError\n",
    "            if rb <= start or end <= lb or lb == rb: # 区间无交集，递归终止\n",
    "                return 0\n",
    "            elif lb <= start and end <= rb: # 区间全覆盖，递归终止\n",
    "                return self.treelis[node].val\n",
    "            else:\n",
    "                self.push_lazy_down(start, end, node) # lazy标记下发\n",
    "                mid = (start + end) >> 1\n",
    "                lnode = node * 2; rnode = node * 2 + 1\n",
    "                tl = self.get_section_val(start, mid, lb, rb, lnode)\n",
    "                tr = self.get_section_val(mid,   end, lb, rb, rnode)\n",
    "                return tl + tr\n",
    "            \n",
    "        def set_section_increas(self, start: int, end: int, lb: int, rb: int, \n",
    "                            inc=1, node: int=1):\n",
    "            '''给定区间内所有值，增加特定  inc'''\n",
    "            if lb > rb: # 给定区间越界判断\n",
    "                raise IndexError\n",
    "            if rb <= start or end <= lb or lb == rb: # 区间无交集，递归终止\n",
    "                pass\n",
    "            elif lb <= start and end <= rb: # 区间全覆盖，递归终止\n",
    "                # 修改节点 val  值\n",
    "                self.treelis[node].val += (end - start) * inc\n",
    "                # 修改节点 lazy 值\n",
    "                self.treelis[node].lazy += inc\n",
    "                \n",
    "            else:\n",
    "                self.push_lazy_down(start, end, node) # lazy标记下发\n",
    "                mid = (start + end) >> 1\n",
    "                lnode = node * 2; rnode = node * 2 + 1\n",
    "                self.set_section_increas(start, mid, lb, rb, inc, lnode)\n",
    "                self.set_section_increas(mid,   end, lb, rb, inc, rnode)\n",
    "                self.treelis[node].val = self.treelis[lnode].val +\\\n",
    "                                        self.treelis[rnode].val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "\n",
    "class SegmentTreeNode:\n",
    "    def __init__(self, lo, hi) -> None:\n",
    "        self.lo = lo\n",
    "        self.hi = hi\n",
    "        self.val = 0\n",
    "        self.lazy = 0\n",
    "        if lo + 1 < hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            self.left = SegmentTreeNode(lo, mid)\n",
    "            self.right = SegmentTreeNode(mid, hi)\n",
    "\n",
    "    def update(self, val):\n",
    "        self.lazy += val\n",
    "        self.val += val * (self.hi - self.lo)\n",
    "\n",
    "    def query(self, lo, hi):\n",
    "        if self.lo >= lo and self.hi <= hi:\n",
    "            res = self.val\n",
    "            self.update(1)\n",
    "            return res\n",
    "        mid = (self.lo + self.hi) // 2\n",
    "        res = 0\n",
    "        self.left.update(self.lazy)\n",
    "        self.right.update(self.lazy)\n",
    "        self.lazy = 0\n",
    "        if lo < mid:\n",
    "            res += self.left.query(lo, hi)\n",
    "        if hi > mid:\n",
    "            res += self.right.query(lo, hi)\n",
    "        self.val = self.left.val + self.right.val\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: list[int]) -> int:\n",
    "        last_idx_dict = {}\n",
    "        segment_tree = SegmentTreeNode(0, len(nums))\n",
    "        res = 0\n",
    "        curr_res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            last_idx = last_idx_dict.get(num, -1) + 1\n",
    "            curr_res = (\n",
    "                curr_res + i - last_idx + 1 + 2 * segment_tree.query(last_idx, i + 1)\n",
    "            ) % MOD\n",
    "            res += curr_res\n",
    "            last_idx_dict[num] = i\n",
    "        return res % MOD"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
